On Wed, Jan 17, 2018 at 06:25:03PM +0100, Otto Moerbeek wrote:
> On Wed, Jan 17, 2018 at 01:59:21PM +0000, kshe wrote:
>
> > Hi,
> >
> > In malloc_bytes(), the choice of the chunk_info list to use is
> > correlated with that of the offset at which the search for a free chunk
> > begins, because both use the same random source. This is easy to avoid,
> > for example by doing something like the diff below.
> >
> > --- malloc.c.orig Sun Jan 14 11:18:10 2018
> > +++ malloc.c Tue Jan 16 12:31:29 2018
> > @@ -954,7 +954,7 @@ malloc_bytes(struct dir_info *d, size_t size, void *f)
> > wrterror(d, "chunk info corrupted");
> >
> > if (bp->free > 1)
> > - bp->rotor += r;
> > + bp->rotor += getrbyte(d);
> > i = bp->rotor++ & (bp->total - 1);
> >
> > /* start somewhere in a short */
>
> This has been done to save a random byte. The correlation does not hurt.
>
> >
> > On a related note, however, I have some doubts about the usefulness of
> > this "randomisation rotor".
> >
> > First, it currently does not really randomise anything, since on most
> > architectures the total number of chunks always divides 256, so that
> > using merely `r' as the random offset instead of `bp->rotor + r' would
> > not change the distribution for the random variable thus obtained.
> > Moreover, in the rare cases where it actually has a noticeable effect,
> > this distribution is no longer uniform (and very biased) anyway, so the
> > proper way to randomise these choices would be to call getrbyte() twice,
> > not to add one random byte to a previously used random byte.
>
> The point is that on some arch there are more than 256 chunks in a
> page. e.g. on sparc64 (pagesize is 8k) for 16 bytes chunks. So using
> just a byte is not enough to count all chunks. That's why I'm
> collecting more bits by adding them to previously generated bits. Bias
> is not a big deal here as well.
>
> >
> > Second, it was introduced to "remember the position of the last free bit
> > in chunk_info", but it does not do that at all. In fact, when chunks
> > are allocated uniformly (which is always the case on amd64 for example),
> > once only two free slots are left, if the search for the first of these
> > two takes n steps, the search for the second and last one is then
> > guaranteed to take at least n steps, as it will systematically repeat
> > the last n-1 unsuccessful steps of the previous one, which is actually
> > worse than simply starting at a random offset or, for that matter, from
> > the beginning of the bitmap.
>
> Looking at this code again I see your point. I seems some assignment
> to the rotor has been lost in the refactoring.
>
> I'll revisit.
>
> -Otto
>
> >
> > More precisely, if n is the total number of chunks, the average number
> > of bits to check in order to find the last two free chunks is
> >
> > (n + 1) / 3 + (n + 1) / 2
> >
> > if both starting offsets are chosen randomly and independently from each
> > other. On the other hand, the current average number of bits that will
> > be checked is n, or more explicitly
> >
> > (n + 1) / 3 + 2 * (n + 1) / 3 - 1,
> >
> > or even more explicitly
> >
> > (sum for i = 1 to n of
> > i * 2 * (n - i) / (n * (n - 1))) +
> > (sum for i = 1 to n of
> > i * 2 * (i - 1) / (n * (n - 1))) - 1.
> >
> > This indeed becomes worse than the above for all n greater than 5, that
> > is for all cases except the two least important ones (n = 2 and n = 4),
> > where no optimisation is necessary anyway.
> >
> > Therefore, I think this variable should be removed from chunk_info, as
> > it currently does more harm than good. If this is agreed with, I could
> > also provide a diff for it (but the solution, by the way, is not to
> > revert to the previous version of this code, which did not make much
> > sense either).
> >
> > Regards,
> >
> > kshe
Looking back the rotor thing is ill-convceived indeed. I'm now
testing the diff below. I still re-use r, because I really think a
little bit of correlation does not hurt here.
-Otto
Index: malloc.c
===================================================================
RCS file: /cvs/src/lib/libc/stdlib/malloc.c,v
retrieving revision 1.240
diff -u -p -r1.240 malloc.c
--- malloc.c 18 Jan 2018 08:37:28 -0000 1.240
+++ malloc.c 18 Jan 2018 08:51:10 -0000
@@ -172,7 +172,6 @@ struct chunk_info {
u_short free; /* how many free chunks */
u_short total; /* how many chunks */
u_short offset; /* requested size table offset */
- u_short rotor; /* randomization rotor */
u_short bits[1]; /* which chunks are free */
};
@@ -953,9 +952,13 @@ malloc_bytes(struct dir_info *d, size_t
if (bp->canary != (u_short)d->canary1)
wrterror(d, "chunk info corrupted");
- if (bp->free > 1)
- bp->rotor += r;
- i = bp->rotor++ & (bp->total - 1);
+ if (bp->free > 1) {
+ i = r;
+ if (bp->total > UCHAR_MAX)
+ i = (i << 8) + getrbyte(d);
+ i &= (bp->total - 1);
+ } else
+ i = 0;
/* start somewhere in a short */
lp = &bp->bits[i / MALLOC_BITS];
