]> git.baikalelectronics.ru Git - kernel.git/commit
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)
commitaaa70b757929e52b289371122b6865a3a7734b45
treec0dec74d805acf86be80430adb82cea0105668cd
parent68299fabaeb02a32382c438fa962f88fd24a5e15
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