About TODO Blog RSS Old blog Projects Gallery Notes

Wed, 02 Aug 2006

Network tree allocator.


Userspace model has been completed.
I have not run stress tests yet, but it already can allocate set of objects and combine them back when they are freed. Let's see an example:

• allocate 120 bytes
• allocate 200 bytes
• allocate 70 bytes


• free 120 bytes
• free 70 bytes
• free 200 bytes

• get one page
• split it to 120 and PAGE_SIZE-120 bytes parts
• mark PAGE_SIZE-120 bytes part as free and move it's container into new list
• split PAGE_SIZE-120 into 200 and PAGE_SIZE-120-200 bytes parts (second allocation)
• mark PAGE_SIZE-120-200 bytes part as free and move it's container into new list
• split PAGE_SIZE-120-200 into 70 and PAGE_SIZE-120-200-70 bytes parts (third allocation)
• mark PAGE_SIZE-120-200-70 bytes part as free and move it's container into new list


• free first chunk (120 bytes) - it was first in the page and it does not have free neighbours (above 200 bytes allocation was done right after this chunk and it is used)
• allocate new container and add it into the list for 120 bytes (aligned to AVL_MIN_SIZE actually) free objects
• free third chunk (70 bytes) - it has a big free area at the left (note that I'm talking about little endian here), of PAGE_SIZE-120-200-70 bytes and second allocated (currently used) chunk of 200 bytes at the right, so this freeing reuse container from the left chunk and move it into the list for PAGE_SIZE-120-200-70+70 bytes
• free 200 bytes chunk - it has both free neighbours: with PAGE_SIZE-120-200-70+70 bytes and 120 bytes. So it will reuse container for 120 bytes, so it results in PAGE_SIZE chunk.

PAGE_SIZE: 4096, max nodes: 4094, node size: 32.
avl_update_node: node: 0x523800, value: 02554000, ptr: 0x2554000, cpos: 127, size: 128, num: 4.
avl_fill_bits: num: 4, pos: 0, idx: 0, p: f, start: 0, stop: 4, fffffffffffffff0.
avl_update_node: reuse container 0x2555f60 in pos 123 with ptr 0x2554080.
main: allocated ptr: 0x2554000, size: 120.

avl_update_node: node: 0x523800, value: 02554000, ptr: 0x2554080, cpos: 123, size: 224, num: 7.
avl_fill_bits: num: 7, pos: 4, idx: 0, p: 7f0, start: 4, stop: 11, fffffffffffff800.
avl_update_node: reuse container 0x2555f60 in pos 116 with ptr 0x2554160.
main: allocated ptr: 0x2554080, size: 200.

avl_update_node: node: 0x523800, value: 02554000, ptr: 0x2554160, cpos: 116, size: 96, num: 3.
avl_fill_bits: num: 3, pos: 11, idx: 0, p: 3800, start: 11, stop: 14, ffffffffffffc000.
avl_update_node: reuse container 0x2555f60 in pos 113 with ptr 0x25541c0.
main: allocated ptr: 0x2554160, size: 70.

avl_free: ptr: 0x2554000 [02554000], pos: 0, sbits: 4, size: 120.
avl_fill_bits: num: 4, pos: 0, idx: 0, p: f, start: 0, stop: 4, ffffffffffffc00f.
avl_combine: lp: (nil), lbits: 0, lc: (nil), rp: (nil), rbits: 0, rc: (nil), 
	current: ptr: 0x2554000, bits: 4, combined: ptr: 0x2554000, idx: 3, cont: (nil).
avl_combine: Added new container for pointer 0x2554000, size: 128.
main: freed ptr: 0x2554000.

avl_free: ptr: 0x2554160 [02554000], pos: 11, sbits: 3, size: 70.
avl_fill_bits: num: 3, pos: 11, idx: 0, p: 3800, start: 11, stop: 14, fffffffffffff80f.
avl_free: found free left neighbour at 0x25541c0, bits: 114.
avl_combine: lp: 0x25541c0, lbits: 114, lc: 0x2555f60, rp: (nil), rbits: 0, rc: (nil), 
	current: ptr: 0x2554160, bits: 3, combined: ptr: 0x2554160, idx: 116, cont: 0x2555f60.
avl_combine: Using existing container for pointer 0x2554160, size: 3744.
main: freed ptr: 0x2554160.

avl_free: ptr: 0x2554080 [02554000], pos: 4, sbits: 7, size: 200.
avl_fill_bits: num: 7, pos: 4, idx: 0, p: 7f0, start: 4, stop: 11, ffffffffffffffff.
avl_free: found free left neighbour at 0x2554160, bits: 117.
avl_free: found free right neighbour at 0x2554000, bits: 4.
avl_combine: lp: 0x2554160, lbits: 117, lc: 0x2555f60, rp: 0x2554000, rbits: 4, rc: 0x2555f80, 
	current: ptr: 0x2554080, bits: 7, combined: ptr: 0x2554000, idx: 127, cont: 0x2555f80.
avl_combine: Using existing container for pointer 0x2554000, size: 4096.
main: freed ptr: 0x2554080.

Completed.

/devel/networking/nta :: Link / Comments (0)

Comments are closed for this story.