# Overview
## Structures and variables
Global variable:
```c
zone_hastable_t zone_table; // pointer to zone_hashtable
uint64_t cookie[2]; // security check
```
There is one and only a `zone_table` which contains a pointer to an **array of zones pointer**.
```c
struct zone_hashtable {
uint32_t capacity; // size of this hashtable
uint32_t num_zone; // current number of zone in this hashtable
uint32_t page_size; // size of memory page
struct zone zone_bootstrap; // bootstrap zone attached in zone_hashtable to allocate a zone object
zone_t zones[]; // array of zone_t pointer
};
```
### Zone
A zone manages a circular linked list of pages, each page is a region which stores several objects of the **same size** (same for all page in a zone) - called **chunk**. A zone has a name, a capacity, ... Beside that, there's a balanced tree to maintain pages that have the same name hash (which is used to determine page index).
```c
struct zone {
char zone_name[MAX_ZONE_NAME];
uint32_t flags:1;
uint32_t object_size; // size of each object
uint32_t capacity; // maximum number of objects store in this zone
uint32_t num_allocation; // current number of allocation object
uint32_t num_freed; // current number of free object
uint32_t num_page_mapped; // number of page mapped in this zone
page_mapped_t page_mapped_head; // point to head of mapped page
page_mapped_t page_min_num_free; // point to page has smallest number of free chunk
page_mapped_t page_min_num_alloc; // point to page has largest number of free chunk
// because hashtable could have duplicate item
// we add this Balance Tree for each node in hashtable to store duplicate item
// to make sure when we search a zone by name the time complexity is O(log(N))
BLTREE_ROOT_DECL(blnode);
};
```
A page is managed in the form of `struct page_mapped`. Note that the real memory region of chunks in page starts from `page->base_address`, which follows **right after** the `struct page_mapped` within the same `mmap` region. See below:
```c
struct page_mapped {
uint32_t mapped_capacity;
uint32_t mapped_num_allocation;
uint32_t mapped_num_free;
uint32_t page_size;
void *base_address;
void *cur_address;
page_mapped_t next;
page_mapped_t prev;
uint64_t bitmap[];
};
// mmap region:
// struct page_mapped;
// base_address starts from here
```
```c
// page_mapped_t map_new_page(size_t object_size) { ...
new_page = (page_mapped_t)mmap(NULL, page_size, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_ANONYMOUS, -1, 0);
if((int64_t)new_page == -1){
return NULL;
}
bzero((void *)new_page, sizeof(struct page_mapped) + nbit_map);
new_page->mapped_capacity = n_object;
new_page->base_address = (void *)((uint8_t *)new_page + size_page_mapped);
new_page->cur_address = new_page->base_address; // cur_address looks like top_chunk :D
```
🎍 On init (`constructor()`), `COOKIE` is randomized and `zone_table` is initialized. Several zones of different `object_size` is created for `zmalloc` (not `zone_malloc`, see more at section [Default zones for serving size request](https://hackmd.io/@_qR67wP7RW69RHBACDVAdQ/S1zUxNTUC#Default-zones-for-serving-size-request-zmalloc)). These `size` values are predefined.
```c
#define ZMALLOC_SIZE_ARRAY_LENGTH 19
const uint32_t zmalloc_size_array[] = {16, 32, 48, 64, 80, 96, 128, 160, 192, 256, 320, 384, 448, 512, 768, 1024, 2048, 4096, 8192};
void zmalloc_init()
{
uint32_t zmalloc_size = 0;
for(int i = 0; i < ZMALLOC_SIZE_ARRAY_LENGTH; i++){
zmalloc_size = zmalloc_size_array[i];
snprintf(zmalloc_zone_name[i], MAX_MALLOC_NAME_LEN, "zmalloc.%d", zmalloc_size);
#ifdef ZMALLOC_INIT_FIRST
zone_create_internal(zmalloc_zone_name[i], zmalloc_size, false);
#endif
}
}
```
😭 However, `ZMALLOC_INIT_FIRST` was not specified (on `cmake`, said `@SeaDragnoL` - i tested with remote). Hence, all zones `"zmalloc.%d"` have never been created - just declared the name.
That's why whenever `zfree("zmalloc.64")` is called, the program exits, as my input below:
```py
create_secret(b"a ", b"pass", Key(3, b"k"*3), Secret(65, b"v"*65))
# Output
Invalid zone zmalloc.64
[*] Got EOF while reading in interactive
```
**[DEBUG]**: Last 16 bytes: our `COOKIE` XD Must be it
Zone create:
## Page operations
There are 2 page operations that are notable:
```c
page_mapped_t map_new_page(size_t object_size);
bool page_unmap_page(page_mapped_t unmap_page);
```
To put it simply, this is just `mmap` and `unmap`stuffs.
## Zone operations
Let's take a look at operations on `zone`: `zone_create`, `zone_alloc` or `zone_free` are all wrapper for their internal function.
```c
__BEGIN_DECLS
void zone_create(const char *zone_name, uint32_t object_size); // create a new zone for specific object
void* zone_alloc(const char *zone_name); // alloc a new object
void zone_free(const char *zone_name, void *ptr); // free an object
#ifdef DEBUG
void zone_list();
void zone_list2();
#endif
#ifdef USEZMALLOC
#define MIN_CHUNK_SIZE 0x10
#define ZMALLOC_SIZE_ARRAY_LENGTH 19
const uint32_t zmalloc_size_array[] = {16, 32, 48, 64, 80, 96, 128, 160, 192, 256, 320, 384, 448, 512, 768, 1024, 2048, 4096, 8192};
void* zmalloc(size_t size);
void* zcalloc(size_t count, size_t object_size);
void* zrealloc(void *old_ptr, size_t old_size, size_t size);
void zfree(void *ptr, size_t ptr_size);
#endif
__END_DECLS
```
### `zone_create_internal (const char* name, object_size, bool is_mapped)`
Here are the steps when a new zone is created and added to the `zone_table`.
1. Check whether the number of zone has reached `capacity` yet.
2. Are there already a zone with the same `name`?
3. Alloc a chunk from bootstrap zone to storage.
4. Zone index is calculated by a weak hash function. If the entry in that index is empty, put it there.
5. Otherwise, put it in the balanced tree of that index (which root is the first zone having that index).
If you wonder what was that `zone_alloc_internal("zone_bootstrap")`, then actually it's just allocating a chunk from bootstrap zone for a new zone's storage. The new zone will then be initialized by `zone_init()`.
```c
// allocating a new temporary zone
d_zone = (zone_t)zone_alloc_internal(Z_ZONE_BOOTSTRAP_NAME);
if(!d_zone){
panic("Unable to create zone %s\n", zone_name);
}
bzero((void *)d_zone, sizeof(struct zone));
strncpy(d_zone->zone_name, zone_name, sizeof(zone->zone_name) - 1);
d_zone->flags |= Z_ZONE_CHILD;
```
If `is_mapped` is set, the head page (also the first) is created via `map_new_page()` which is a wrapper of `mmap(NULL, page_size, RW, MAP_PRIVATE|MAP_ANONYMOUS, -1, 0)`.
### `zone_destroy (zone_t zonep)`
Iterate through all pages, call `munmap()` and clear everything to 0. If a zone was created in `zone_bootstrap`, then free it.
```c
if(zone_flags & Z_ZONE_CHILD){
// free a zone was created in zone_bootstrap
zone_free_internal(Z_ZONE_BOOTSTRAP_NAME, zonep);
}
```
### `zone_alloc_internal (const char *zone_name)`
Allocate a chunk from a specific zone. Recall that each zone only provides chunk of a fixed size which was specified on init. That is `zone->object_size`.
1. If there is NO freed chunks to reuse on this zone, go back to the "shrink style" on `page_min_num_alloc` like how `glibc malloc` do with top chunk.
2. Otherwise, keep taking from the one with smallest number of freed chunk: `page_min_num_free` until there are no available freed chunk, then update new `page_min_num_free` from the remaining ones.
#### 1. No freed chunk to reuse
**If there is no freed chunk to reuse**, it starts to find in `pagep = zone->page_min_num_alloc` (which is the page having **largest** number of free chunk), take the current address of that page and increase the current address an amount of `zone->object_size`. This is similar to **shrinking the top chunk in glibc's malloc**.
```c
if(!zone->num_freed) {
// we don't have any freed chunk to reuse
if(zone->page_min_num_alloc && \
zone->page_min_num_alloc->mapped_num_allocation + 1 < zone->page_min_num_alloc->mapped_capacity){
// hack way to get new chunk
pagep = zone->page_min_num_alloc;
#ifdef USECOOKIE
if(memcmp(PAGEMAP_COOKIE_PTR(pagep), (void *)&cookie, sizeof(cookie)) != 0){
panic("Corrupted `pagep` of zone %s\n", zone->zone_name);
}
#endif
if(pagep->mapped_num_allocation + 1 < pagep->mapped_capacity){
alloc_new_pointer:
ret_ptr = pagep->cur_address;
pagep->cur_address = (void *)((size_t)pagep->cur_address + zone->object_size);
#ifdef USECOOKIE
memcpy(CHUNK_COOKIE_PTR(ret_ptr, zone->object_size - sizeof(cookie)), \
(void *)&cookie, sizeof(cookie));
#endif
pagep->mapped_num_allocation++;
zone->num_allocation++;
goto return_ptr;
}
}
```
Beside that, if `COOKIE` security feature is enable, it will first check whether the cookie remains as `PAGEMAP_COOKIE_PTR(pagep)`. `COOKIE` is fixed. Are there any ways to leak it?
```c
#define PAGEMAP_COOKIE_PTR(pagep) \
(void *)((uint8_t *)pagep + \
round_up(sizeof(struct page_mapped) + round_up(pagep->mapped_capacity, BIT_ARRAY_SIZE) / BIT_PER_BYTE, 2 * sizeof(size_t)))
```
#### 2. Use freed chunk
It starts to find in the page that has **smallest** number of freed chunk. The taken chunk's index is computed by `bitmap_find_idx(pagep->bitmap, pagep->mapped_capacity)`.
What is that?
```c
uint64_t bitmap_find_idx(uint64_t *bitmap, int bitmap_size)
{
uint64_t chunk_idx = -1LL;
int i, k;
int n_loop = round_up(bitmap_size, BIT_ARRAY_SIZE) / BIT_ARRAY_SIZE;
for(i = 0; i < n_loop; i++){
if(bitmap[i] & (uint64_t)(~0ULL)){
// found suitable chunk
for(k = 0; k < BIT_ARRAY_SIZE; k++){
if(BIT64_IS_SET(bitmap[i], k)){
chunk_idx = i*BIT_ARRAY_SIZE + k;
break;
}
}
break;
}
}
return chunk_idx;
}
```
I kinda feel like it's just finding the first available entry in a table of `n_loop x BIT_ARRAY_SIZE`:
🎍 That's how they store chunks on a page huh?
Then it clears taken entry from the bitmap "array". See how the variable changes:
```c
BIT64_CLEAR(pagep->bitmap[idx], bit_idx);// mark this chunk was allocated
ret_ptr = (void *)((uint8_t *)pagep->base_address + chunk_idx * zone->object_size);
pagep->mapped_num_allocation++;
pagep->mapped_num_free--;
zone->num_allocation++;
zone->num_freed--;
if(zone->page_min_num_free->mapped_num_free == 0){
zone->page_min_num_free = NULL;
}
```
**Summary:** It keeps taking chunks from the page with minimum number of freed chunk (or, maximum number of available chunk).
### `zone_free_internal (const char *zone_name, void *ptr)`
Steps for freeing a pointer from a zone:<br>
1. Check whether the `zone_name` is valid.<br>
2. Check if `ptr` is in page region `[pagep->base_address, end_address)` <br>
3. Check for `ptr` alignment (whether `ptr - pagep->base_address` is divisible by `zone->object_size`)<br>
4. Check whether `CHUNK_COOKIE_PTR(ptr,..)` matches global variable `uint64_t cookie[2];`<br>
5. Check double free when the `bitmap` value is set to `1` already.<br>
6. Otherwise, this is a valid free operation. Mark the `bitmap` value to `1` and update values. <br>
7. If the entire page has been freed, remove it from the zone. Then update `zone->page_min_num_alloc` for later use.
```c
// Valid free operation
BIT64_SET(pagep->bitmap[idx], bit_idx); // mark this chunk is freed
pagep->mapped_num_allocation--;
pagep->mapped_num_free++;
zone->num_allocation--;
zone->num_freed++;
```
Remove page from zone:
```c
#define PAGEMAP_REMOVE(zone, pagep) do { \
page_mapped_t ppage; \
if(PAGEMAP_HEAD(zone) == pagep) {\
ppage = PAGEMAP_HEAD(zone)->next; \
ppage->prev = PAGEMAP_TAIL(zone); \
PAGEMAP_TAIL(zone)->next = ppage; \
PAGEMAP_HEAD(zone) = ppage; \
} else if(PAGEMAP_TAIL(zone) == pagep) { \
ppage = PAGEMAP_TAIL(zone)->prev; \
ppage->next = PAGEMAP_HEAD(zone); \
PAGEMAP_TAIL(zone) = ppage; \
} else {\
for(ppage = PAGEMAP_HEAD(zone); ppage->next != pagep; ppage = ppage->next); \
ppage->next = pagep->next; \
pagep->next->prev = ppage; \
}\
}while(0)
```
## Default zones for serving size request: `zmalloc`
There are default zones for allocating chunk of fixed size. These are not defined by the user, but libzone itself. Their names are of the form `"zmalloc.{size}"` where `size` values are predefined as we can see at the following section.
To allocate, instead of calling `zone_alloc (zone_name)`, simply do a `zmalloc (size)`.
In `db`, these `zmalloc.%d` zones are used when it comes to internal array allocation for `ArrayTemplate` or `DictTemplate` once the array size exceeds default size and no longer be able to stored in the `inline_array`.
> **Remark.** So what is the difference compared to user-defined zones (`ZONE_REGISTER`)?<br> **Answer.** User-defined zones serve Object request. And object size are fixed, of course. `zone_alloc` allocats memory for a new Object, whereas `zmalloc` simply allocates memory for a `size` request and it doesn't care what you store within that region.
### `zmalloc(size_t size)`
Return a chunk for request of `size`. A wrapper of `zmalloc_alloc_internal()`.
Request for a `size` exceed 8192 will result error. These numbers are `0x10-`aligned. That's it, when we create a zone with a size of i.e `0x37`, `zone_init` will then increase its size for storing `COOKIE` and alignment.
```c
#define ZMALLOC_SIZE_ARRAY_LENGTH 19
const uint32_t zmalloc_size_array[] = {16, 32, 48, 64,
80, 96, 128, 160, 192, 256, 320, 384, 448,
512, 768, 1024, 2048, 4096, 8192};
```
```c
void* zmalloc(size_t size)
{
uint64_t malloc_size;
char *zmalloc_zone_name = NULL;
zone_t zone = NULL;
if(zmalloc_get_zone_name((uint64_t)size, &malloc_size, &zmalloc_zone_name) == E_BIG){
LOG("zmalloc size is tool big\n");
return NULL;
}
ZONE_LCK;
zone = zone_table_get_zone(zmalloc_zone_name);
ZONE_UNLCK;
if(!zone){
// this zmalloc_zone_name wasn't allocated, then allocate it
zone_create(zmalloc_zone_name, malloc_size);
}
return zone_alloc_internal(zmalloc_zone_name);
}
```
This function is used for allocating `T* array`, like `IOBytes`. `IOString` inherits `IOBytes`, `IOSymbol` inherits `IOString`, so they are exactly the same. When a new instance obtained via `new` operator (i.e `zmake_shared`), the memory for the class is taken from the correct zone like `IOBytes`, or `IOSymbol`, etc. via `zone_alloc ()`. However, the internal array `array[]` once exceed `DEFAULT_SIZE = 64`, it will call `zmalloc` for storing raw `c_str`. That means our string's length should not exceed 8192 bytes.
```c
template <typename T>
class ArrayTemplate {
private:
T inlinearray[DEFAULT_SIZE];
T* array;
size_t size;
protected:
// ...
void ensure(size_t needed_size) {
size_t realloc_size = 0;
T* new_array = NULL;
// automatically realloc buffer if count > size
if(count + needed_size > size){
realloc_size = round_up(count + needed_size, size);
new_array = (T *)zcalloc(realloc_size, sizeof(T));
assert(new_array != NULL); // make sure new array is not NULL
// copy old array to new array
memcpy((void *)new_array, (void *)array, sizeof(T) * count);
if((size_t)array != (size_t)inlinearray){
zfree(array, size * sizeof(T));
}
size = realloc_size;
array = new_array;
}
}
```
### `zfree(void *ptr, size_t ptr_size)`
Wrapper for `zone_free_internal`.
```c
void zfree(void *ptr, size_t ptr_size)
{
uint64_t malloc_size;
char *zmalloc_zone_name = NULL;
if(zmalloc_get_zone_name((uint64_t)ptr_size, &malloc_size, &zmalloc_zone_name) == E_BIG){
LOG("zmalloc size is tool big\n");
return;
}
zone_free_internal(zmalloc_zone_name, ptr);
}
```
## Chunk structure
There is no metadata except 16-byte COOKIE at the end.
## Summary
- No data is stored in a freed chunk (`COOKIE` has no usage for exploiting yet). Chunks on a page are managed by a bitmap array and there is no optimization. It just iterate through all entry in the table and take the first one that is freed (bitmap set) to serve request.
- We might have a look at IOObject which use libzone for alloc memory.
Sign in with Wallet
Connect another wallet