On Wed, Mar 18, 2020 at 07:29:51AM +0530, Neeraj Pal wrote:
> On Fri, Mar 13, 2020, at 11:45 AM Otto Moerbeek <o...@drijf.net> wrote:
> >
> > Please indent your code snippets.
> yeah, my apologies. I shall indent the code snippets.
>
> >
> > di_info is special. Having a guard page on both sides for regular
> > allocation can be done, but would waste more pages. Note that
> > allocations are already spread throughout the address space, so it is
> > very likely that an allocation is surrounded by unmapped pages.
> >
> Okay, So, as from omalloc_poolinit() code it is not there, but we can do
> but it will be wastage of one-page memory and also entire address space is
> spread with unmapped pages. So, it is very likely that there will some
> unmapped page beside dir_info in the memory.
>
> >
> > We need two pages to store dir_info.
> >
> >
> > > Now, MMAPNONE maps up to len (8192 + (4096 * 2)) = 16384
> >
> > We allocate 4 pages prot none.
> >
> > > then, mprotecting the pages through p + MALLOC_PAGESIZE + DIR_INFO_RSZ
> - 1
> >
> > the two middle pages are r/w.
> >
> > > d_avail = (8192 - 4824) >> 4 = 3368 >> 4 = 210
> > >
> > > Now, d = (p + MALLOC_PAGESIZE + (random_no_under_210 << 4)
> >
> > di_info ends up on an aligned address somewhere in the middle pages on
> > an offset between 0 and (210<<4) = 0..3360, counting from the start of
> > the two middle pages.
> Thank you for the information. So, it is like [(p + MALLOC_PAGESIZE) +
> (0..3360)]. It is kind of like array, For example, let's suppose, x = p +
> MALLOC_PAGESIZE. So, it will be x[0..3360].
> Am I right?
> >
> > MALLOC_CHUNK_LISTS could be increased at the cost of overhead.
> > MALLOC_MAXSHIFT cannot, it is the shift of the max chunk size that fits in
> > a page.
> Okay. I understood. And, yeah more randomization means more cost overhead.
>
> Thank you, Otto, for your detailed information.
>
> Please find the code below:
>
> 948 /*
> 949 * Allocate a chunk
> 950 */
> 951 static void *
> 952 malloc_bytes(struct dir_info *d, size_t size, void *f)
> 953 {
> 954 u_int i, r;
> 955 int j, listnum;
> 956 size_t k;
> 957 u_short *lp;
> 958 struct chunk_info *bp;
> 959 void *p;
> 960
> 961 if (mopts.malloc_canary != (d->canary1 ^
> (u_int32_t)(uintptr_t)d) ||
> 962 d->canary1 != ~d->canary2)
> 963 wrterror(d, "internal struct corrupt");
> 964
> 965 j = find_chunksize(size);
> 966
> 967 r = ((u_int)getrbyte(d) << 8) | getrbyte(d);
> 968 listnum = r % MALLOC_CHUNK_LISTS;
> 969 /* If it's empty, make a page more of that size chunks */
> 970 if ((bp = LIST_FIRST(&d->chunk_dir[j][listnum])) == NULL) {
> 971 bp = omalloc_make_chunks(d, j, listnum);
> 972 if (bp == NULL)
> 973 return NULL;
> 974 }
> 975
> 976 if (bp->canary != (u_short)d->canary1)
> 977 wrterror(d, "chunk info corrupted");
>
>
> Here, in the code mentioned above, we can see that on line 961 and
> line 976. I don't understand why it is checking for
> canaries of malloc_readonly with d and then allocated chunk bp with d,
> because I have seen that validation of canary
> happens in free(3) not in malloc(3). So, it is like there may be some
> cases where one can corrupt these also??
There are several types of canaries. They try to detect corruption of
various meta data structures. There are alo canaries for user allocated
data, they are enabled with the C option.
>
>
> 978
> 979 i = (r / MALLOC_CHUNK_LISTS) & (bp->total - 1);
> 980
> 981 /* start somewhere in a short */
> 982 lp = &bp->bits[i / MALLOC_BITS];
> 983 if (*lp) {
> 984 j = i % MALLOC_BITS;
> 985 k = ffs(*lp >> j);
> 986 if (k != 0) {
> 987 k += j - 1;
> 988 goto found;
> 989 }
> 990 }
> 991 /* no bit halfway, go to next full short */
> 992 i /= MALLOC_BITS;
> 993 for (;;) {
> 994 if (++i >= bp->total / MALLOC_BITS)
> 995 i = 0;
> 996 lp = &bp->bits[i];
> 997 if (*lp) {
> 998 k = ffs(*lp) - 1;
> 999 break;
> 1000 }
> 1001 }
> 1002 found:
> 1003 #ifdef MALLOC_STATS
> 1004 if (i == 0 && k == 0) {
> 1005 struct region_info *r = find(d, bp->page);
> 1006 r->f = f;
> 1007 }
> 1008 #endif
> 1009
> 1010 *lp ^= 1 << k;
> 1011
> 1012 /* If there are no more free, remove from free-list */
> 1013 if (--bp->free == 0)
> 1014 LIST_REMOVE(bp, entries);
> 1015
> 1016 /* Adjust to the real offset of that chunk */
> 1017 k += (lp - bp->bits) * MALLOC_BITS;
> 1018
> 1019 if (mopts.chunk_canaries && size > 0)
> 1020 bp->bits[bp->offset + k] = size;
> 1021
> 1022 k <<= bp->shift;
> 1023
> 1024 p = (char *)bp->page + k;
> 1025 if (bp->size > 0) {
> 1026 if (d->malloc_junk == 2)
> 1027 memset(p, SOME_JUNK, bp->size);
> 1028 else if (mopts.chunk_canaries)
> 1029 fill_canary(p, size, bp->size);
> 1030 }
> 1031 return p;
> 1032 }
>
> And, the calculations above, is it for calculating the offset in the page,
> that is, k. Because I have seen that during free(3) operations, it again
> calculates this offset to find the same. So, is it doing only offset
> calculation?
In general addding an int to a pointer calculates an offset, so yes.
Study whats the role of p and k is. Let the code speak. If you fail to
understand parts, study further and play with it. You'll learn more
from that than asking for confirmation all the time.
-Otto
>
> Please confirm.
>
> Regards,
> Neeraj
