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 */
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.
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.
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
