Re: Strange interrupt behaviour

Linus Torvalds (torvalds@transmeta.com)
Wed, 15 Jul 1998 09:48:23 -0700 (PDT)


On 15 Jul 1998, Harvey J. Stein wrote:
>
> Linus Torvalds <torvalds@transmeta.com> writes:
> >
> > This boils down to how to place the free pages. It's essentially:
> >
> > x * (x-2) * (x-4) * (x-8) * .. (y factors)
> > -----------------------------
> > x * x * x * .. (y factors - ie x^y)
> >
> > and the rate at which point this likelihood shrinks is very fast indeed.
>
> The math isn't quite right. Consider:
>
> 1st hole placed on 1st page.
>
> 2nd hole placed on 4th page.
>
> There are now x-5 places to place the 3rd hole, not x-4.

No, the thing is that you also have to worry about the alignement: we get
a 8kB area only if we have two consecutive 4kB holes that are also
aligned.

As such 0+1 would be a 8kB area, and 4+5 would be one, but 3+4 and 1+2
would not.

Thus the "x-n*2" sequence - for each old hole (n) there is just one
"paired hole" that would cause us to be able to use a 8kB allocation.

> Did you program just count all combinations (so that the numbers you
> posted are correct even if the above is off)?

My numbers are incorrect if the above math is incorrect. I _think_ it is
fine, but I could be just full of it.. But the basic thing is that we're
not just looking for adjacent pages, we're looking for a certain pattern.

Linus

-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.rutgers.edu
Please read the FAQ at http://www.altern.org/andrebalsa/doc/lkml-faq.html