Re: kmalloc() allocation.

Re: kmalloc() allocation.

[Ingo Oeser]

On Mon, Oct 30, 2000 at 02:40:16PM -0200, Rik van Riel wrote:
> > There are 256 megabytes of SDRAM available. I don't think it's
> > reasonable that a 1/2 megabyte allocation would fail, especially
> > since it's the first module being installed.
> If you write the defragmentation code for the VM, I'll
> be happy to bump up the limit a bit ...

Should become easier once we start doing physical page scannings.

We could record physical continous freeable areas on the fly
then. If someone asks for them later, we recheck whether they
still exists and free (inactive_clean) or remap (active or
inactive_dirty) the whole area, whether they are used or not. 

This could still be improved by using up smallest fit areas
first for kmalloc() based on these areas.

But beware: We just have a good hint here, which needs to be
   rechecked every time we allocate such areas to become
   guarantee.

Rik: What do you think about this (physical cont. area cache) for 2.5?

Regards

Ingo Oeser
-- 
Feel the power of the penguin - run linux@your.pc
<esc>:x
--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux.eu.org/Linux-MM/

Re: kmalloc() allocation.

[Rik van Riel]

On Tue, 31 Oct 2000, Ingo Oeser wrote:
> On Mon, Oct 30, 2000 at 02:40:16PM -0200, Rik van Riel wrote:

> > If you write the defragmentation code for the VM, I'll
> > be happy to bump up the limit a bit ...
> 
> Should become easier once we start doing physical page scannings.
> 
> We could record physical continous freeable areas on the fly
> then. If someone asks for them later, we recheck whether they
> still exists and free (inactive_clean) or remap (active or
> inactive_dirty) the whole area, whether they are used or not. 
> 
> This could still be improved by using up smallest fit areas
> first for kmalloc() based on these areas.

> Rik: What do you think about this (physical cont. area cache) for 2.5?

http://www.surriel.com/zone-alloc.html

cheers,

Rik
--
"What you're running that piece of shit Gnome?!?!"
       -- Miguel de Icaza, UKUUG 2000

http://www.conectiva.com/		http://www.surriel.com/

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux.eu.org/Linux-MM/

Re: kmalloc() allocation.

[Richard B. Johnson]

On Tue, 31 Oct 2000, Rik van Riel wrote:

> On Tue, 31 Oct 2000, Ingo Oeser wrote:
> > On Mon, Oct 30, 2000 at 02:40:16PM -0200, Rik van Riel wrote:
> 
> > > If you write the defragmentation code for the VM, I'll
> > > be happy to bump up the limit a bit ...
> > 
> > Should become easier once we start doing physical page scannings.
> > 
> > We could record physical continous freeable areas on the fly
> > then. If someone asks for them later, we recheck whether they
> > still exists and free (inactive_clean) or remap (active or
> > inactive_dirty) the whole area, whether they are used or not. 
> > 
> > This could still be improved by using up smallest fit areas
> > first for kmalloc() based on these areas.
> 
> > Rik: What do you think about this (physical cont. area cache) for 2.5?
> 
> http://www.surriel.com/zone-alloc.html
> 
> cheers,
> 
> Rik
> --

Since Linux is starting to be used in many 'strange' non-desktop
environments, maybe it's time to provide a hook to reserve the
top N kilobytes of RAM for strange buffers. Like:

	append="..,reserve=2M".

Upon startup, a pointer, valid when using the kernel DS, could be
initialized to point to the beginning of this area. This is essentially
zero overhead for the kernel because it just points to one longword
greater than the RAM the kernel will use.

In the event that this is too much work, then an additional entry could
be made in the GDT to address this area, and the resulting segment
number could be included in a kernel header file. To access it, code
would do:

	push	ds
	movl	$RESERVE_MEM, %eax
	movl	%eax,ds
	.....
	DS:[0] now points to its beginning.
	pop	ds

This 'free' area could be used for all kinds of stuff including helping
to relocate/debug come complex things.

The cost to performance is zero. A GDT entry on Intel is 8 bytes.


Cheers,
Dick Johnson

Penguin : Linux version 2.2.17 on an i686 machine (801.18 BogoMips).

"Memory is like gasoline. You use it up when you are running. Of
course you get it all back when you reboot..."; Actual explanation
obtained from the Micro$oft help desk.


--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux.eu.org/Linux-MM/

Re: kmalloc() allocation.

[afei]

On Tue, 31 Oct 2000, Ingo Oeser wrote:

> On Mon, Oct 30, 2000 at 02:40:16PM -0200, Rik van Riel wrote:
> > > There are 256 megabytes of SDRAM available. I don't think it's
> > > reasonable that a 1/2 megabyte allocation would fail, especially
> > > since it's the first module being installed.
> > If you write the defragmentation code for the VM, I'll
> > be happy to bump up the limit a bit ...
> 
> Should become easier once we start doing physical page scannings.
> 
> We could record physical continous freeable areas on the fly
> then. If someone asks for them later, we recheck whether they
> still exists and free (inactive_clean) or remap (active or
> inactive_dirty) the whole area, whether they are used or not. 

I am confused. Why cannot one simply audit the memory usage and always
have an up-to-date list of free memory pages? When a page is allocated,
the allocator should make a call to move that page outside of the
freelist; and when it is free, just move it back to the free list. Is it
because of the overhead? 

Fei
> 
> This could still be improved by using up smallest fit areas
> first for kmalloc() based on these areas.
> 
> But beware: We just have a good hint here, which needs to be
>    rechecked every time we allocate such areas to become
>    guarantee.
> 
> Rik: What do you think about this (physical cont. area cache) for 2.5?
> 
> Regards
> 
> Ingo Oeser
> -- 
> Feel the power of the penguin - run linux@your.pc
> <esc>:x
> --
> To unsubscribe, send a message with 'unsubscribe linux-mm' in
> the body to majordomo@kvack.org.  For more info on Linux MM,
> see: http://www.linux.eu.org/Linux-MM/
> 

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux.eu.org/Linux-MM/

Re: kmalloc() allocation.

[Ingo Oeser]

On Tue, Oct 31, 2000 at 11:35:46AM -0200, Rik van Riel wrote:
> > Rik: What do you think about this (physical cont. area cache) for 2.5?
                                       ^^^^^^^^^^^^^^^^^^^^^^^^^ == PCAC
> 
> http://www.surriel.com/zone-alloc.html

Read it when you published it first, but didn't notice you still
worked on it ;-)

My approach is still different. We get the HINT for free. And
your zone only shift this problem from page to mem_zone level.

I thought about sth. like this:

/* Adds an physical continuous area of pages to the PCAC.
 * To be implemented later, once we decide on a data structure
 * for this, which can do fast unique insert and at least O(N)
 * retrieve. (Hashes?)
 */
void add_phys_cont_chunk(struct phys_page *start, size_t area_size);

/* Add page(s) to pool, where we prefer to kmalloc() small things
 * and vmalloc() things. This gets us close to a best fit
 * strategy instead of sth. like the first fit we have now.
 */
void add_small_phys_area(struct phys_page *start, size_t area_size);

/* Gets a chunk of at least area_size pages and removes it from
 * the PCAC or NULL of none found.
 *
 * To be implemented later along with the above routine.
 */
struct phys_page *get_phys_cont_chunk(size_t area_size);

#define suitable(p) (moveable(p) || freeable(p)) /* refine this */
#define MIN_PHYS_CHUNK 2 /* tune this */

/* in physical page scan to transfer REFERENCED bit */

   size_t area_size = 0;
   struct phys_page *p, *chunk_start;

   p = prev = first_phys_page;

   while (p != last_phys_page) {
      if (area_size) {
         if (suitable(p)) { 
         
            /* expand recent chunk */
            area_size++;

         } else {
         
            /* insert last chunk */
            if (area_size >= MIN_PHYS_CHUNK) 
               add_phys_cont_chunk(chunk_start, area_size);
            else add_small_phys_area(chunk_start, area_size);
            area_size = 0;
         }
      } else {
         if (suitable(p)) {

            /* start new chunk */
            area_size = 1;
            chunk_start = p;
         }
      }
      p = p->next;
   }

And later, when we need a physically continuous area >= MIN_PHYS_CHUNK:

   /* lookup PCAC for a hint */
   struct phys_page *s = get_phys_cont_chunk(area_size);
   
   if (s) {
      size_t a = area_size;
      struct phys_page *p = s;
      
      /* lock down page tables */
      while (a--) {
         if ( ! free_or_move_page(p) )
            break;
         p = p->next;
      }
      /* unlock page tables*/
      if (!a) 
         return s; /* hey, it worked! */

   } else {
      /* no hints, try it the old way or fail */
   }


Hope it sound not too stupid ;-)

Regards 

Ingo Oeser
-- 
Feel the power of the penguin - run linux@your.pc
<esc>:x
--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux.eu.org/Linux-MM/

Re: kmalloc() allocation.

[Rik van Riel]

On Tue, 31 Oct 2000, Ingo Oeser wrote:
> On Tue, Oct 31, 2000 at 11:35:46AM -0200, Rik van Riel wrote:
> > > Rik: What do you think about this (physical cont. area cache) for 2.5?
>                                        ^^^^^^^^^^^^^^^^^^^^^^^^^ == PCAC
> > 
> > http://www.surriel.com/zone-alloc.html
> 
> Read it when you published it first, but didn't notice you still
> worked on it ;-)
> 
> My approach is still different. We get the HINT for free. And
> your zone only shift this problem from page to mem_zone level.

It's a nice idea, but you still want to be sure you won't
allocate eg. page tables randomly in the middle of the
PCACs ;)

regards,

Rik
--
"What you're running that piece of shit Gnome?!?!"
       -- Miguel de Icaza, UKUUG 2000

http://www.conectiva.com/		http://www.surriel.com/

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux.eu.org/Linux-MM/

Re: kmalloc() allocation.

[Ingo Oeser]

On Tue, Oct 31, 2000 at 02:11:24PM -0200, Rik van Riel wrote:
[PCAC]
> It's a nice idea, but you still want to be sure you won't
> allocate eg. page tables randomly in the middle of the
> PCACs ;)

Yes. That's why we check later, whether our hint is still true.

If we cannot free or move all pages from this area, we retry by
looking up the PCAC again (which I forgot to show, because I was
in a hurry :-/ ), or try the old method and might fail there.

So we have only an idea, where we MIGHT have an physical area of
this size, but have no idea whether it is STILL freeable or
movable.

That's why I didn't care about ANY locking[1]. The only thing, that
I take for granted, is that all struct phys_page are linked
together and represent the whole systems physical memory
including holes. Anything that breaks these assumption must be
fixed in my code.

Once you have implemented physical page scanning, I'll try to
implement this. I just needed to know, whether you like the idea,
or it is total crap ;-)

Another problem is, that the PCAC needs memory to store these
areas. One possibility is to store in in struct phys_page and
have a global hash table for the sizes. But these are details for
2.5 and not for now ;-)

Regards

Ingo Oeser

[1] Later I have to lock the PCAC related structures of course.
-- 
Feel the power of the penguin - run linux@your.pc
<esc>:x
--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux.eu.org/Linux-MM/