Uploaded image for project: 'WiredTiger'
  1. WiredTiger
  2. WT-14457

Add bitstring functions to find the first set/clear bit from a given start bit and improve related code

    • Type: Icon: Improvement Improvement
    • Resolution: Unresolved
    • Priority: Icon: Major - P3 Major - P3
    • None
    • Affects Version/s: None
    • None
    • Storage Engines, Storage Engines - Persistence
    • None
    • 5

      Currently, _bit_ffs and _bit_ffc only find the first set or clear bit across the entire bitmap. However, in live_restore_fs.c, there are several places that need to find the first set or clear bit starting from a given bit. Adding such functions would simplify the code and improve time efficiency.

      This ticket is to:
      1. Add two functions to find first set and clear bit from a given start bit in bitstring_inline.h.
      2. Change the logic of how we fill hole during _wti_live_restore_fs_restore_file. Currently we are calling live_restore_fill_hole until all holes are filled however in each run we are calling _bit_ffc to find the first clear bit from the beginning of the bitmap and this is O(n^2). Instead we can memorise the last bit offset we filled and try to find the first clear bit from that in the next run.
      3. Rewrite __live_restore_can_service_read a bit, this function essentially is trying to verify a range in the bitmap follows the pattern 1*0*(zero or more set bits followed by zero or more clear bits), return if whole range can be read from destination and find first clear bit in the range. We are iterating through the range bit by bit at the moment and this can be improved.
      4. There is a logic in __live_restore_decode_bitmap to assert any bits exceeding the file size are set, this happens when we have truncated a file causing filesize on disk shorter than that in the bitmap itself. This can be improved as well since we are currently iterating through the range bit by bit.
      5. There's a proposal to modify bitstring_inline.h to use uint64_t instead of uint8_t to improve the performance, if that's too complex to implement it in this ticket(or keeps as a low priority and never get done) please split it to a new ticket.

            Assignee:
            backlog-server-storage-engines [DO NOT USE] Backlog - Storage Engines Team
            Reporter:
            zunyi.liu@mongodb.com Zunyi Liu
            Votes:
            0 Vote for this issue
            Watchers:
            1 Start watching this issue

              Created:
              Updated: