]> git.proxmox.com Git - mirror_ubuntu-kernels.git/commit - fs/ntfs3/index.c
fs/ntfs3: Limit binary search table size
authorKari Argillander <kari.argillander@gmail.com>
Thu, 2 Sep 2021 15:40:48 +0000 (18:40 +0300)
committerKonstantin Komarov <almaz.alexandrovich@paragon-software.com>
Mon, 13 Sep 2021 16:41:46 +0000 (19:41 +0300)
commit162333efa8dc4984d2ca0a2eb85528e13366f271
treec0dec74d805acf86be80430adb82cea0105668cd
parent9c2aadd0fdf88a7ebeebd1e97a9c66b07ad3e14a
fs/ntfs3: Limit binary search table size

Current binary search allocates memory for table and fill whole table
before we start actual binary search. This is quite inefficient because
table fill will always be O(n). Also if table is huge we need to
reallocate memory which is costly.

This implementation use just stack memory and always when table is full
we will check if last element is <= and if not start table fill again.
The idea was that it would be same cost as table reallocation.

Signed-off-by: Kari Argillander <kari.argillander@gmail.com>
Signed-off-by: Konstantin Komarov <almaz.alexandrovich@paragon-software.com>
fs/ntfs3/index.c