Fork us on GitHub Follow us on Facebook Follow us on Twitter

Changeset 79b5bc9 in mainline


Ignore:
Timestamp:
2012-06-03T15:01:41Z (8 years ago)
Author:
Frantisek Princ <frantisek.princ@…>
Branches:
master
Children:
da9f220d
Parents:
4585bda
Message:

very malicious bug in binary search algorithm

File:
1 edited

Legend:

Unmodified
Added
Removed
  • uspace/lib/ext4/libext4_extent.c

    r4585bda r79b5bc9  
    262262        uint16_t entries_count = ext4_extent_header_get_entries_count(header);
    263263
    264         // Check trivial situation
    265         if (entries_count == 1) {
    266                 *index = EXT4_EXTENT_FIRST_INDEX(header);
    267                 return;
    268         }
    269 
    270264        // Initialize bounds
    271265        l = EXT4_EXTENT_FIRST_INDEX(header) + 1;
    272         r = l + entries_count - 1;
     266        r = EXT4_EXTENT_FIRST_INDEX(header) + entries_count - 1;
    273267
    274268        // Do binary search
     
    307301        }
    308302
    309         // Check trivial situation
    310         if (entries_count == 1) {
    311                 *extent = EXT4_EXTENT_FIRST(header);
    312                 return;
    313         }
    314 
    315303        // Initialize bounds
    316304        l = EXT4_EXTENT_FIRST(header) + 1;
    317         r = l + entries_count - 1;
     305        r = EXT4_EXTENT_FIRST(header) + entries_count - 1;
    318306
    319307        // Do binary search
    320         while (l < r) {
     308        while (l <= r) {
    321309                m = l + (r - l) / 2;
    322310                uint32_t first_block = ext4_extent_get_first_block(m);
     
    365353        // Walk through extent tree
    366354        ext4_extent_header_t *header = ext4_inode_get_extent_header(inode_ref->inode);
     355
     356//      EXT4FS_DBG("inode = \%u", inode_ref->index);
     357//      EXT4FS_DBG("count = \%u", ext4_extent_header_get_entries_count(header));
     358
    367359        while (ext4_extent_header_get_depth(header) != 0) {
    368360
     
    395387        } else {
    396388
     389//              EXT4FS_DBG("required = \%u, first = \%u, start = \%u, count = \%u", iblock, ext4_extent_get_first_block(extent), (uint32_t)ext4_extent_get_start(extent), ext4_extent_get_block_count(extent));
     390
    397391                // Compute requested physical block address
    398392                uint32_t phys_block;
    399                 phys_block = ext4_extent_get_start(extent) + iblock;
    400                 phys_block -= ext4_extent_get_first_block(extent);
     393                uint32_t first = ext4_extent_get_first_block(extent);
     394                phys_block = ext4_extent_get_start(extent) + iblock - first;
     395
     396//              phys_block = ext4_extent_get_start(extent) + iblock;
     397//              phys_block -= ext4_extent_get_first_block(extent);
    401398
    402399                *fblock = phys_block;
Note: See TracChangeset for help on using the changeset viewer.