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
