Potentially incorrect BUCKET/BLOCK ARRAY SIZE

[StrongerXi]

Example

Environment
Tests compiled and executed in docker

Test case
Simply add the following "test" to hash_table_page_test.cpp, and run it.

TEST(HashTablePageTest, SizeTest) {
  struct Val {
    char data_[4094];
  };
  using KeyType = char;
  using ValueType = struct Val;
  using TestBucketPage = HashTableBucketPage<KeyType, ValueType, int*(int, int)>;
  LOG_INFO("sizeof(ValueType) = %lu", sizeof(ValueType));
  LOG_INFO("sizeof(MappingType) = %lu", sizeof(MappingType));
  LOG_INFO("BUCKET_ARRAY_SIZE = %lu", BUCKET_ARRAY_SIZE);
  LOG_INFO("sizeof(TestBucketPage) = %lu (ignoring bucket content)", sizeof(TestBucketPage));
}

Relevant output:

.../bustub/test/container/hash_table_page_test.cpp:33:TestBody] INFO  - sizeof(ValueType) = 4094
.../bustub/test/container/hash_table_page_test.cpp:34:TestBody] INFO  - sizeof(MappingType) = 4095
.../bustub/test/container/hash_table_page_test.cpp:35:TestBody] INFO  - BUCKET_ARRAY_SIZE = 1
.../bustub/test/container/hash_table_page_test.cpp:36:TestBody] INFO  - sizeof(TestBucketPage) = 2 (ignoring bucket content)

Note that the real size of TestBucketPage is sizeof(TestBucketPage) + BUCKET_ARRAY_SIZE * sizeof(MappingType) = 2 + 4095 = 4097, which exceeds PAGE_SIZE = 4096.

Expected output:

Running in docker, we should expect to see the following:

...
.../bustub/test/container/hash_table_page_test.cpp:35:TestBody] INFO  - BUCKET_ARRAY_SIZE = 0
...

However, when running on my machine (MacOS Big Sur 11.6, M1 chip), the program won't even compile, i.e., the following line would trigger an "array too large" error. Note this is actually helpful, since it prevents people from instantiating "too large" pages.

char occupied_[(BUCKET_ARRAY_SIZE - 1) / 8 + 1];

Explanation

First of all, consider these 2 size calculations:

#define BUCKET_ARRAY_SIZE (4 * PAGE_SIZE / (4 * sizeof(MappingType) + 1))
char occupied_[(BUCKET_ARRAY_SIZE - 1) / 8 + 1];

As far as I can see, they are equivalent to

#define BUCKET_ARRAY_SIZE floor_div(PAGE_SIZE, sizeof(MappingType) + 0.25)
char occupied_[ceil_div(BUCKET_ARRAY_SIZE, 8)];

Now consider extensible hash table pages (same reasoning applies to linear hash table pages).

The real size of HashTableBucketPage is

2 * ceil_div(BUCKET_ARRAY_SIZE / 8) + BUCKET_ARRAY_SIZE * sizeof(MappingType)

Which gives us the following series of inequalities:

PAGE_SIZE >= 2 * ceil_div(BUCKET_ARRAY_SIZE / 8) + BUCKET_ARRAY_SIZE * sizeof(MappingType)
          >= 2 + 2 * (BUCKET_ARRAY_SIZE / 8) + BUCKET_ARRAY_SIZE * sizeof(MappingType)
          >= 2 + (BUCKET_ARRAY_SIZE / 4) - 1 + BUCKET_ARRAY_SIZE * sizeof(MappingType)
           = 1 + BUCKET_ARRAY_SIZE * (sizeof(MappingType) + 0.25)

Which reduces down to the following constraint

BUCKET_ARRAY_SIZE <= floor_div(PAGE_SIZE - 1, sizeof(MappingType) + 0.25)

Which means the BUCKET_ARRAY_SIZE should be defined as this:

#define BUCKET_ARRAY_SIZE (4 * (PAGE_SIZE - 1) / (4 * sizeof(MappingType) + 1))

Proposal

1. Changing the following macros in hash_table_page_defs.h

#define BLOCK_ARRAY_SIZE (4 * PAGE_SIZE / (4 * sizeof(MappingType) + 1))
#define BUCKET_ARRAY_SIZE (4 * PAGE_SIZE / (4 * sizeof(MappingType) + 1))

into

#define BLOCK_ARRAY_SIZE (4 * (PAGE_SIZE - 1) / (4 * sizeof(MappingType) + 1))
#define BUCKET_ARRAY_SIZE (4 * (PAGE_SIZE - 1) / (4 * sizeof(MappingType) + 1))

2. Explicitly document that we are simulating floor division and ceiling division.