On Fri, Mar 27, 2020 at 02:21:44PM +0530, Neeraj Pal wrote:
> 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.
For chunk size 256, there will indeed be 16 chunks in a page. i will
*not* be 255 in that case, but 15. There is no such thing as
MALLOC_BYTES. the memset will becomes memset(p->bits, 0xff, 2) and
set p->bits[0] to to 0xffff The line below it will set p->bits[1] to
(2<<15) - 1 = 0xffff; So all 16 bits needed are set to 1.
The debug session below is for chunk size 16, so the numbers are different.
>
> 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
You need to look at the bigger picture.
Depending on the chunk size, a different number of bits are needed,
since the amount of chunks in a page differs.
In OpenBSD, struct chunk_info is a variable size data structure. In
alloc_chunk_info() the size needed to store the struct itself plus
the shorts needed for the bitmap and the canary info (if enabled) is
computed.
For a chunk of half a page, we need two bits, so a single short is enough.
For chunk size 16, we need MALLOC_PAGESIZE/16 bits for the bitmap.
That translates to (MALLOC_PAGESIZE/16)/2 shorts. The rest of the
calculation adjust for the other fields in chunk_info.
-Otto
