"traversal failed: u: Bad message" when deleting an extremely large directory in Linux

Okay, I finally solved the issues. It was due to the filesystem errors that cause ls to display wrongly, and other utilities to malfunction.
I'm sorry that the question title is misleading (despite that there are indeed many files inside u/, the directory is not extremely large).

I solved the problem by using a live usb since the corrupted filesystem is /. The fix was simply applying sudo fsck -cfk /dev/sda2 where dev/sda2 is the corrupted disk.

You can't remove huge quantities of files using rm. You can either do

find u/ -type f -print0 | xargs -r -0 rm -f

this will delete only files; to delete everything, use

find u/ -print0 | xargs -r -0 rm -rf

you can probably use the --delete option of find, if your system has it:

find u/ -type f --delete

or the funky method with rsync:

mkdir emptyfolder
rsync -r --delete emptyfolder/ u/

rsync is way faster than rm when deleting things as it will bypass some checks.

You can try find /u -type f | while read f; do rm -f $f; done This will take a while but might work. For some reason, loops in bash works well when other approaches fails.