| Bug #44469 | my_bitmap overallocates the memory | ||
|---|---|---|---|
| Submitted: | 24 Apr 2009 18:58 | Modified: | 29 Apr 2009 8:04 |
| Reporter: | Konstantin Osipov (OCA) | Email Updates: | |
| Status: | Verified | Impact on me: | |
| Category: | MySQL Server | Severity: | S3 (Non-critical) |
| Version: | 5.0, 5.1, 6.0 bzr | OS: | Any |
| Assigned to: | CPU Architecture: | Any | |
[29 Apr 2009 8:04]
Sveta Smirnova
Thank you for the report. Verified as described.
[30 Apr 2009 17:14]
MySQL Verification Team
Storing and retrieving values as words vs. bytes is much faster for nearly all modern CPUs and memory systems. I think that storing the bitmap in 4-byte chunks will give much faster data throughput than trying to read single-bytes from the heap. Would you prefer that we work faster, but with a little extra storage or that we work slower and save a few bytes per row? I understand the optimization that you propose but with non-8-bit CPUs it requires a little extra overhead to work data that is not the native word-length for the processor. I think that the overhead of the extra bytes are well spent for the speed improvement it provides.
[2 May 2009 12:27]
Konstantin Osipov
The bug is not in how the bitmap is stored, but how bit offset is calculated. Currently there is a bug in calculation of offsets, that renders 3 out of 4 bytes of the integer unusable.
Description: In the bitmap code, we assume that we work with 8-bit integers when we access, set or modify the bits in the bitmap. I.e. the bitmap arithmetic is always 8-based. However, the bitmap array itself is defined as an array of 32-bit integers. Thus we waste 3 bytes of space for each 8 bits of the bitmap. The code: typedef uint32 my_bitmap_map; typede struct st_bitmap { my_bitmap_map *bitmap; ... my_bitmap_map last_word_mask; my_bitmap_map *last_word_ptr; }; But the bitmap manipulation defines are: #define bitmap_buffer_size(bits) (((bits)+31)/32)*4 #define no_bytes_in_map(map) (((map)->n_bits + 7)/8) #define no_words_in_map(map) (((map)->n_bits + 31)/32) #define bytes_word_aligned(bytes) (4*((bytes + 3)/4)) #define _bitmap_set_bit(MAP, BIT) (((uchar*)(MAP)->bitmap)[(BIT) / 8] \ |= (1 << ((BIT) & 7))) #define _bitmap_flip_bit(MAP, BIT) (((uchar*)(MAP)->bitmap)[(BIT) / 8] \ ^= (1 << ((BIT) & 7))) #define _bitmap_clear_bit(MAP, BIT) (((uchar*)(MAP)->bitmap)[(BIT) / 8] \ &= ~ (1 << ((BIT) & 7))) #define _bitmap_is_set(MAP, BIT) (uint) (((uchar*)(MAP)->bitmap)[(BIT) / 8] \ & (1 << ((BIT) & 7))) Notice the 8-bit based arithmetics. How to repeat: See description. Suggested fix: Don't waste 3 bytes of space per each byte. This may reveal some out-of-bounds access bugs as well. Add asserts to make sure there are no out-of-bounds accesses.