On Wed, Mar 25, 2020 at 2:06 AM Otto Moerbeek <[email protected]> wrote:
> pp points to a page of chunks
> bp point to the associated meta info: a bitmap that says which chunks
> in the page are free. The bitmap is an aray of shorts, so 16 bits per
> entry.
>
per entry means for our case bits[1], so only one entry?
in the code k is first is the chunk number, and then multiplied (by
> shifting it by bp->shift) to get the byte offset of the chunk inside
> the chunk page.
>
Okay, so, here, we have 3 things:
1. pp is the page
2. k is the chunknum, before shiting, which means k is the index for the
chunk in the page pp.
3. After shifting, k becomes the byte offset of the chunk inside the pp
page.
p->bits is a bit mask. Each short in it holds 16 bits, so the first 16
> chunks end uo in the first short, the next in the 2nd short etc.
>
> The *lp ^= 1 << k line actuall sets the bit.
>
Okay, 16 chunks because each chunk has different bit and a total of 16 bits
represents 16 different chunks.
So, as per the init_chunk_info() function. for the bitmap operations given
below:
840
841 /* set all valid bits in the bitmap */
842 i = p->total - 1;
843 memset(p->bits, 0xff, sizeof(p->bits[0]) * (i / MALLOC_BITS));
844 p->bits[i / MALLOC_BITS] = (2U << (i % MALLOC_BITS)) - 1;
845 }
Here, it first calculates the i, which is 256 - 1, that is, 255 or in other
words 0xff.
Then, the memset(3) writes the len bytes of "0xff" to p->bits.
Here, len is sizeof(p-bits[0]) * (i / MALLOC_BITS), where
sizeof(p->bits[0]) = 2bytes and (i / MALLOC_BYTES) is 255 / 16, that is,
15. And total it becomes, 2 * 15 = 30bytes.
So, it copies 30 bytes of 0xff to p->bits. But here, the main confusion
lies, like the bits[1] is of type u_short and as we know the sizeof u_short
is 2bytes but we are copying the 30 bytes through memset(3).
Then, in the next line, it is again making the 2 bytes to 0xff through
calculating the last index of bit array. That is,
p->bits[255 / 16] = (2U << (255 % 16)) - 1
p->bits[15] = 65536 - 1 = 65535, which, is 0xffff.
So, after overall calculations, it is copying the 30 bytes over to the
sizeof(u_short), which is 2 bytes.
Below are the observations from the debugger:
openbsd# LD_PRELOAD=/usr/src/lib/libc/obj/libc.so.95.1 gdb -q sample
(gdb) br main
Breakpoint 1 at 0x1363: file sample.c, line 7.
(gdb) r 12345
Starting program: /root/test/sample 12345
Breakpoint 1 at 0xfa68fc8a363: file sample.c, line 7.
Error while reading shared library symbols:
Dwarf Error: wrong version in compilation unit header (is 4, should be 2)
[in module /usr/libexec/ld.so]
Breakpoint 1, main (argc=2, argv=0x7f7ffffea018) at sample.c:7
7 char *buff1, *buff2 = NULL;
Current language: auto; currently minimal
(gdb) s
8 buff1 = (char *)malloc(8);
(gdb) s
malloc (size=8) at /usr/src/lib/libc/stdlib/malloc.c:1293
1293 int saved_errno = errno;
(gdb) br init_chunk_info
Breakpoint 2 at 0xfa951dafa20: file /usr/src/lib/libc/stdlib/malloc.c, line
832.
(gdb) c
Continuing.
Breakpoint 2, init_chunk_info (d=0xfa9011de110, p=0xfa910ecedb0, bits=4)
at /usr/src/lib/libc/stdlib/malloc.c:832
832 if (bits == 0) {
(gdb) n
838 p->shift = bits;
(gdb)
839 p->total = p->free = MALLOC_PAGESIZE >> p->shift;
(gdb)
840 p->size = 1U << bits;
(gdb)
841 p->offset = howmany(p->total, MALLOC_BITS);
(gdb)
843 p->canary = (u_short)d->canary1;
(gdb)
846 i = p->total - 1;
(gdb)
848 memset(p->bits, 0xff, sizeof(p->bits[0]) * (i / MALLOC_BITS));
(gdb) x/30wx p->bits
0xfa910ecedd4: 0x00000000 0x00000000 0x00000000 0x00000000
0xfa910ecede4: 0x00000000 0x00000000 0x00000000 0x00000000
0xfa910ecedf4: 0x00000000 0x00000000 0x00000000 0x00000000
0xfa910ecee04: 0x00000000 0x00000000 0x00000000 0x00000000
0xfa910ecee14: 0x00000000 0x00000000 0x00000000 0x00000000
0xfa910ecee24: 0x00000000 0x00000000 0x00000000 0x00000000
0xfa910ecee34: 0x00000000 0x00000000 0x00000000 0x00000000
0xfa910ecee44: 0x00000000 0x00000000
(gdb) p/x i
$1 = 0xff
(gdb) n
849 p->bits[i / MALLOC_BITS] = (2U << (i % MALLOC_BITS)) - 1;
(gdb) x/30wx p->bits
0xfa910ecedd4: 0xffffffff 0xffffffff 0xffffffff
0xffffffff
0xfa910ecede4: 0xffffffff 0xffffffff 0xffffffff
0x0000ffff
0xfa910ecedf4: 0x00000000 0x00000000 0x00000000 0x00000000
0xfa910ecee04: 0x00000000 0x00000000 0x00000000 0x00000000
0xfa910ecee14: 0x00000000 0x00000000 0x00000000 0x00000000
0xfa910ecee24: 0x00000000 0x00000000 0x00000000 0x00000000
0xfa910ecee34: 0x00000000 0x00000000 0x00000000 0x00000000
0xfa910ecee44: 0x00000000 0x00000000
(gdb) p/x i / 16
$2 = 0xf
(gdb) n
850 }
As we can see above it copied the 0xff to 30 bytes, and still, the last
2bytes are 0.
then after the line no. 849, it calculates p->bits[15] which seems to be
the last remaining bytes. And, making them 0xffff.
(gdb) x/30wx p->bits
0xfa910ecedd4: 0xffffffff 0xffffffff 0xffffffff
0xffffffff
0xfa910ecede4: 0xffffffff 0xffffffff 0xffffffff
0xffffffff
0xfa910ecedf4: 0x00000000 0x00000000 0x00000000 0x00000000
0xfa910ecee04: 0x00000000 0x00000000 0x00000000 0x00000000
0xfa910ecee14: 0x00000000 0x00000000 0x00000000 0x00000000
0xfa910ecee24: 0x00000000 0x00000000 0x00000000 0x00000000
0xfa910ecee34: 0x00000000 0x00000000 0x00000000 0x00000000
0xfa910ecee44: 0x00000000 0x00000000
(gdb) n
Also, I have read the mail
https://marc.info/?l=openbsd-tech&m=131537857923062&w=2, where the u_short
bits[(MALLOC_PAGESIZE / MALLOC_MINSIZE) / MALLOC_BITS], which means
bits[15], changed to bits[1].
And, that change is because of making the chunk_info a variable-sized
struct and wasting less space for metadata.
So, in short, it seems that change is due to space improvement.
And, as from the code snippet of phkmalloc, given below,
/* set all valid bits in the bitmap */
k = bp->total;
i = 0;
/* Do a bunch at a time */
for(;k-i >= MALLOC_BITS; i += MALLOC_BITS)
bp->bits[i / MALLOC_BITS] = ~0;
Here, in my understanding, it seems that it is making the all the 16 bits
to 1 but the same code logic is little different on OpenBSD.
So, for the above observations to copy 30bytes (excluding the 2 bytes of
u_short). Is that due to some improvements that I am missing to understand?
Thanks,
Neeraj
