Re: [rfc][patch] slob: improvements
On Fri, 13 Jul 2007 13:35:06 -0500 Matt Mackall <[EMAIL PROTECTED]> wrote: > On Fri, Jul 13, 2007 at 11:27:25AM -0700, Randy Dunlap wrote: > > > Index: linux-2.6/init/Kconfig > > > === > > > --- linux-2.6.orig/init/Kconfig > > > +++ linux-2.6/init/Kconfig > > > @@ -529,7 +529,7 @@ config SLUB > > > way and has enhanced diagnostics. > > > > > > config SLOB > > > - depends on EMBEDDED && !SPARSEMEM > > > + depends on EMBEDDED && !SPARSEMEM && !ARCH_USES_SLAB_PAGE_STRUCT > > > bool "SLOB (Simple Allocator)" > > > help > > > SLOB replaces the SLAB allocator with a drastically simpler > > > > Is this patch going in? I have a randconfig (2.6.22) with > > CONFIG_SLOB=y > > CONFIG_NUMA=y > > CONFIG_SMP=y > > The kernel build fails with these config symbols set like that. > > It looks like SLOB needs that additional > > && !ARCH_USES_SLAB_PAGE_STRUCT > > (or && !SMP) > > I think Andrew intends to push it to 2.6.23, yes. > Yup. I had to hunt for it though. Turns out I renamed the patch to slob-rework-freelist-handling. Please don't give patches dopey titles like "slob improvements". - To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to [EMAIL PROTECTED] More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
Re: [rfc][patch] slob: improvements
On Fri, Jul 13, 2007 at 11:27:25AM -0700, Randy Dunlap wrote: > > Index: linux-2.6/init/Kconfig > > === > > --- linux-2.6.orig/init/Kconfig > > +++ linux-2.6/init/Kconfig > > @@ -529,7 +529,7 @@ config SLUB > >way and has enhanced diagnostics. > > > > config SLOB > > - depends on EMBEDDED && !SPARSEMEM > > + depends on EMBEDDED && !SPARSEMEM && !ARCH_USES_SLAB_PAGE_STRUCT > > bool "SLOB (Simple Allocator)" > > help > >SLOB replaces the SLAB allocator with a drastically simpler > > Is this patch going in? I have a randconfig (2.6.22) with > CONFIG_SLOB=y > CONFIG_NUMA=y > CONFIG_SMP=y > The kernel build fails with these config symbols set like that. > It looks like SLOB needs that additional > && !ARCH_USES_SLAB_PAGE_STRUCT > (or && !SMP) I think Andrew intends to push it to 2.6.23, yes. -- Mathematics is the supreme nostalgia of our time. - To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to [EMAIL PROTECTED] More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
Re: [rfc][patch] slob: improvements
On Wed, 16 May 2007 01:33:47 +0200 Nick Piggin wrote: > On Tue, May 15, 2007 at 10:17:31AM -0500, Matt Mackall wrote: > > On Tue, May 15, 2007 at 10:43:05AM +0200, Nick Piggin wrote: > > > This patch goes on top of my previous RCU patch, and has various > > > improvements for slob I noticed while implementing said patch ;) > > > > > > Comments? > > > > I'm warming to this. Please check that the comment block at the top is > > still accurate. > > It wasn't, fixed. > > ... > > Here is an updated version. > --- > > Improve slob by turning the freelist into a list of pages using struct page > fields, then each page has a singly linked freelist of slob blocks via a > pointer in the struct page. > > - The first benefit is that the slob freelists can be indexed by a smaller > type (2 bytes, if the PAGE_SIZE is reasonable). > > - Next is that freeing is much quicker because it does not have to traverse > the entire freelist. Allocation can be slightly faster too, because we can > skip almost-full freelist pages completely. > > - Slob pages are then freed immediately when they become empty, rather than > having a periodic timer try to free them. This gives efficiency and memory > consumption improvement. > > > Then, we don't encode seperate size and next fields into each slob block, > rather we use the sign bit to distinguish between "size" or "next". Then > size 1 blocks contain a "next" offset, and others contain the "size" in > the first unit and "next" in the second unit. > > - This allows minimum slob allocation alignment to go from 8 bytes to 2 > bytes on 32-bit and 12 bytes to 2 bytes on 64-bit. In practice, it is > best to align them to word size, however some architectures (eg. cris) > could gain space savings from turning off this extra alignment. > > > Then, make kmalloc use its own slob_block at the front of the allocation > in order to encode allocation size, rather than rely on not overwriting > slob's existing header block. > > - This reduces kmalloc allocation overhead similarly to alignment reductions. > > - Decouples kmalloc layer from the slob allocator. > > > Then, add a page flag specific to slob pages. > > - This means kfree of a page aligned slob block doesn't have to traverse > the bigblock list. > > > I would get benchmarks, but my test box's network doesn't come up with > slob before this patch. I think something is timing out. Anyway, things > are faster after the patch. > > Code size goes up about 1K, however dynamic memory usage _should_ be > lower even on relatively small memory systems. > > Signed-off-by: Nick Piggin <[EMAIL PROTECTED]> > > --- > Index: linux-2.6/init/Kconfig > === > --- linux-2.6.orig/init/Kconfig > +++ linux-2.6/init/Kconfig > @@ -529,7 +529,7 @@ config SLUB > way and has enhanced diagnostics. > > config SLOB > - depends on EMBEDDED && !SPARSEMEM > + depends on EMBEDDED && !SPARSEMEM && !ARCH_USES_SLAB_PAGE_STRUCT > bool "SLOB (Simple Allocator)" > help > SLOB replaces the SLAB allocator with a drastically simpler Is this patch going in? I have a randconfig (2.6.22) with CONFIG_SLOB=y CONFIG_NUMA=y CONFIG_SMP=y The kernel build fails with these config symbols set like that. It looks like SLOB needs that additional && !ARCH_USES_SLAB_PAGE_STRUCT (or && !SMP) --- ~Randy *** Remember to use Documentation/SubmitChecklist when testing your code *** - To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to [EMAIL PROTECTED] More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
Re: [rfc][patch] slob: improvements
On Wed, 16 May 2007 01:33:47 +0200 Nick Piggin wrote: On Tue, May 15, 2007 at 10:17:31AM -0500, Matt Mackall wrote: On Tue, May 15, 2007 at 10:43:05AM +0200, Nick Piggin wrote: This patch goes on top of my previous RCU patch, and has various improvements for slob I noticed while implementing said patch ;) Comments? I'm warming to this. Please check that the comment block at the top is still accurate. It wasn't, fixed. ... Here is an updated version. --- Improve slob by turning the freelist into a list of pages using struct page fields, then each page has a singly linked freelist of slob blocks via a pointer in the struct page. - The first benefit is that the slob freelists can be indexed by a smaller type (2 bytes, if the PAGE_SIZE is reasonable). - Next is that freeing is much quicker because it does not have to traverse the entire freelist. Allocation can be slightly faster too, because we can skip almost-full freelist pages completely. - Slob pages are then freed immediately when they become empty, rather than having a periodic timer try to free them. This gives efficiency and memory consumption improvement. Then, we don't encode seperate size and next fields into each slob block, rather we use the sign bit to distinguish between size or next. Then size 1 blocks contain a next offset, and others contain the size in the first unit and next in the second unit. - This allows minimum slob allocation alignment to go from 8 bytes to 2 bytes on 32-bit and 12 bytes to 2 bytes on 64-bit. In practice, it is best to align them to word size, however some architectures (eg. cris) could gain space savings from turning off this extra alignment. Then, make kmalloc use its own slob_block at the front of the allocation in order to encode allocation size, rather than rely on not overwriting slob's existing header block. - This reduces kmalloc allocation overhead similarly to alignment reductions. - Decouples kmalloc layer from the slob allocator. Then, add a page flag specific to slob pages. - This means kfree of a page aligned slob block doesn't have to traverse the bigblock list. I would get benchmarks, but my test box's network doesn't come up with slob before this patch. I think something is timing out. Anyway, things are faster after the patch. Code size goes up about 1K, however dynamic memory usage _should_ be lower even on relatively small memory systems. Signed-off-by: Nick Piggin [EMAIL PROTECTED] --- Index: linux-2.6/init/Kconfig === --- linux-2.6.orig/init/Kconfig +++ linux-2.6/init/Kconfig @@ -529,7 +529,7 @@ config SLUB way and has enhanced diagnostics. config SLOB - depends on EMBEDDED !SPARSEMEM + depends on EMBEDDED !SPARSEMEM !ARCH_USES_SLAB_PAGE_STRUCT bool SLOB (Simple Allocator) help SLOB replaces the SLAB allocator with a drastically simpler Is this patch going in? I have a randconfig (2.6.22) with CONFIG_SLOB=y CONFIG_NUMA=y CONFIG_SMP=y The kernel build fails with these config symbols set like that. It looks like SLOB needs that additional !ARCH_USES_SLAB_PAGE_STRUCT (or !SMP) --- ~Randy *** Remember to use Documentation/SubmitChecklist when testing your code *** - To unsubscribe from this list: send the line unsubscribe linux-kernel in the body of a message to [EMAIL PROTECTED] More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
Re: [rfc][patch] slob: improvements
On Fri, 13 Jul 2007 13:35:06 -0500 Matt Mackall [EMAIL PROTECTED] wrote: On Fri, Jul 13, 2007 at 11:27:25AM -0700, Randy Dunlap wrote: Index: linux-2.6/init/Kconfig === --- linux-2.6.orig/init/Kconfig +++ linux-2.6/init/Kconfig @@ -529,7 +529,7 @@ config SLUB way and has enhanced diagnostics. config SLOB - depends on EMBEDDED !SPARSEMEM + depends on EMBEDDED !SPARSEMEM !ARCH_USES_SLAB_PAGE_STRUCT bool SLOB (Simple Allocator) help SLOB replaces the SLAB allocator with a drastically simpler Is this patch going in? I have a randconfig (2.6.22) with CONFIG_SLOB=y CONFIG_NUMA=y CONFIG_SMP=y The kernel build fails with these config symbols set like that. It looks like SLOB needs that additional !ARCH_USES_SLAB_PAGE_STRUCT (or !SMP) I think Andrew intends to push it to 2.6.23, yes. Yup. I had to hunt for it though. Turns out I renamed the patch to slob-rework-freelist-handling. Please don't give patches dopey titles like slob improvements. - To unsubscribe from this list: send the line unsubscribe linux-kernel in the body of a message to [EMAIL PROTECTED] More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
Re: [rfc][patch] slob: improvements
On Fri, Jul 13, 2007 at 11:27:25AM -0700, Randy Dunlap wrote: Index: linux-2.6/init/Kconfig === --- linux-2.6.orig/init/Kconfig +++ linux-2.6/init/Kconfig @@ -529,7 +529,7 @@ config SLUB way and has enhanced diagnostics. config SLOB - depends on EMBEDDED !SPARSEMEM + depends on EMBEDDED !SPARSEMEM !ARCH_USES_SLAB_PAGE_STRUCT bool SLOB (Simple Allocator) help SLOB replaces the SLAB allocator with a drastically simpler Is this patch going in? I have a randconfig (2.6.22) with CONFIG_SLOB=y CONFIG_NUMA=y CONFIG_SMP=y The kernel build fails with these config symbols set like that. It looks like SLOB needs that additional !ARCH_USES_SLAB_PAGE_STRUCT (or!SMP) I think Andrew intends to push it to 2.6.23, yes. -- Mathematics is the supreme nostalgia of our time. - To unsubscribe from this list: send the line unsubscribe linux-kernel in the body of a message to [EMAIL PROTECTED] More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
Re: [rfc][patch] slob: improvements
On Tue, May 15, 2007 at 10:17:31AM -0500, Matt Mackall wrote: > On Tue, May 15, 2007 at 10:43:05AM +0200, Nick Piggin wrote: > > This patch goes on top of my previous RCU patch, and has various > > improvements for slob I noticed while implementing said patch ;) > > > > Comments? > > I'm warming to this. Please check that the comment block at the top is > still accurate. It wasn't, fixed. > > +/* > > + * slob_block has a field 'units', which indicates size of block if +ve, > > + * or offset of next block if -ve (in SLOB_UNITs). > > + * > > + * Free blocks of size 1 unit simply contain the offset of the next block. > > + * Those with larger size contain their size in the first SLOB_UNIT of > > + * memory, and the offset of the next free block in the second SLOB_UNIT. > > + */ > > +#if PAGE_SIZE <= (32*1024) > > +typedef s16 slobidx_t; > > +#else > > +typedef s32 slobidx_t; > > +#endif > > This math is wrong because you're doing pointer math on slobidx_ts: It is misleading. But the max is 32K, because INT16_MAX is only 32767. Well actually, if you factor in the minimum alignment requirement, then it does indeed go up to 64K pages. Here is an updated version. --- Improve slob by turning the freelist into a list of pages using struct page fields, then each page has a singly linked freelist of slob blocks via a pointer in the struct page. - The first benefit is that the slob freelists can be indexed by a smaller type (2 bytes, if the PAGE_SIZE is reasonable). - Next is that freeing is much quicker because it does not have to traverse the entire freelist. Allocation can be slightly faster too, because we can skip almost-full freelist pages completely. - Slob pages are then freed immediately when they become empty, rather than having a periodic timer try to free them. This gives efficiency and memory consumption improvement. Then, we don't encode seperate size and next fields into each slob block, rather we use the sign bit to distinguish between "size" or "next". Then size 1 blocks contain a "next" offset, and others contain the "size" in the first unit and "next" in the second unit. - This allows minimum slob allocation alignment to go from 8 bytes to 2 bytes on 32-bit and 12 bytes to 2 bytes on 64-bit. In practice, it is best to align them to word size, however some architectures (eg. cris) could gain space savings from turning off this extra alignment. Then, make kmalloc use its own slob_block at the front of the allocation in order to encode allocation size, rather than rely on not overwriting slob's existing header block. - This reduces kmalloc allocation overhead similarly to alignment reductions. - Decouples kmalloc layer from the slob allocator. Then, add a page flag specific to slob pages. - This means kfree of a page aligned slob block doesn't have to traverse the bigblock list. I would get benchmarks, but my test box's network doesn't come up with slob before this patch. I think something is timing out. Anyway, things are faster after the patch. Code size goes up about 1K, however dynamic memory usage _should_ be lower even on relatively small memory systems. Signed-off-by: Nick Piggin <[EMAIL PROTECTED]> --- mm/slob.c | 271 +- 1 file changed, 200 insertions(+), 71 deletions(-) Index: linux-2.6/mm/slob.c === --- linux-2.6.orig/mm/slob.c +++ linux-2.6/mm/slob.c @@ -7,53 +7,145 @@ * * The core of SLOB is a traditional K style heap allocator, with * support for returning aligned objects. The granularity of this - * allocator is 8 bytes on x86, though it's perhaps possible to reduce - * this to 4 if it's deemed worth the effort. The slob heap is a - * singly-linked list of pages from __get_free_page, grown on demand - * and allocation from the heap is currently first-fit. + * allocator is 4 bytes on 32-bit and 8 bytes on 64-bit, though it + * could be as low as 2 if the compiler alignment requirements allow. + * + * The slob heap is a linked list of pages from __get_free_page, and + * within each page, there is a singly-linked list of free blocks (slob_t). + * The heap is grown on demand and allocation from the heap is currently + * first-fit. * * Above this is an implementation of kmalloc/kfree. Blocks returned - * from kmalloc are 8-byte aligned and prepended with a 8-byte header. + * from kmalloc are 4-byte aligned and prepended with a 4-byte header. * If kmalloc is asked for objects of PAGE_SIZE or larger, it calls * __get_free_pages directly so that it can return page-aligned blocks * and keeps a linked list of such pages and their orders. These * objects are detected in kfree() by their page alignment. * * SLAB is emulated on top of SLOB by simply calling constructors and - * destructors for every SLAB allocation. Objects are returned with - * the 8-byte alignment unless the SLAB_HWCACHE_ALIGN flag is - *
Re: [rfc][patch] slob: improvements
On Tue, May 15, 2007 at 10:43:05AM +0200, Nick Piggin wrote:
> This patch goes on top of my previous RCU patch, and has various
> improvements for slob I noticed while implementing said patch ;)
>
> Comments?
I'm warming to this. Please check that the comment block at the top is
still accurate.
> +/*
> + * slob_block has a field 'units', which indicates size of block if +ve,
> + * or offset of next block if -ve (in SLOB_UNITs).
> + *
> + * Free blocks of size 1 unit simply contain the offset of the next block.
> + * Those with larger size contain their size in the first SLOB_UNIT of
> + * memory, and the offset of the next free block in the second SLOB_UNIT.
> + */
> +#if PAGE_SIZE <= (32*1024)
> +typedef s16 slobidx_t;
> +#else
> +typedef s32 slobidx_t;
> +#endif
This math is wrong because you're doing pointer math on slobidx_ts:
> +static slob_t *slob_next(slob_t *s)
> +{
> + slob_t *base = (slob_t *)((unsigned long)s & PAGE_MASK);
> + slobidx_t next;
> +
> + if (s[0].units < 0)
> + next = -s[0].units;
> + else
> + next = s[1].units;
> + return base+next;
> +}
The max is 64K.
--
Mathematics is the supreme nostalgia of our time.
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to [EMAIL PROTECTED]
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
[rfc][patch] slob: improvements
This patch goes on top of my previous RCU patch, and has various
improvements for slob I noticed while implementing said patch ;)
Comments?
--
Improve slob by turning the freelist into a list of pages using struct page
fields, then each page has a singly linked freelist of slob blocks via a
pointer in the struct page.
- The first benefit is that the slob freelists can be indexed by a smaller
type (2 bytes, if the PAGE_SIZE is reasonable).
- Next is that freeing is much quicker because it does not have to traverse
the entire freelist. Allocation can be slightly faster too, because we can
skip almost-full freelist pages completely.
- Slob pages are then freed immediately when they become empty, rather than
having a periodic timer try to free them. This gives efficiency and memory
consumption improvement.
Then, we don't encode seperate size and next fields into each slob block,
rather we use the sign bit to distinguish between "size" or "next". Then
size 1 blocks contain a "next" offset, and others contain the "size" in
the first unit and "next" in the second unit.
- This allows minimum slob allocation alignment to go from 8 bytes to 2
bytes on 32-bit and 12 bytes to 2 bytes on 64-bit. In practice, it is
best to align them to word size, however some architectures (eg. cris)
could gain space savings from turning off this extra alignment.
Then, make kmalloc use its own slob_block at the front of the allocation
in order to encode allocation size, rather than rely on not overwriting
slob's existing header block.
- This reduces kmalloc allocation overhead similarly to alignment reductions.
- Decouples kmalloc layer from the slob allocator.
Then, add a page flag specific to slob pages.
- This means kfree of a page aligned slob block doesn't have to traverse
the bigblock list.
I would get benchmarks, but my test box's network doesn't come up with
slob before this patch. I think something is timing out. Anyway, things
are faster after the patch.
Code size goes up about 1K, however dynamic memory usage _should_ be
lower even on relatively small memory systems.
---
mm/slob.c | 271 +-
1 file changed, 200 insertions(+), 71 deletions(-)
Index: linux-2.6/mm/slob.c
===
--- linux-2.6.orig/mm/slob.c
+++ linux-2.6/mm/slob.c
@@ -34,26 +34,107 @@
#include
#include
#include
-#include
#include
+#include
+#include
+/*
+ * slob_block has a field 'units', which indicates size of block if +ve,
+ * or offset of next block if -ve (in SLOB_UNITs).
+ *
+ * Free blocks of size 1 unit simply contain the offset of the next block.
+ * Those with larger size contain their size in the first SLOB_UNIT of
+ * memory, and the offset of the next free block in the second SLOB_UNIT.
+ */
+#if PAGE_SIZE <= (32*1024)
+typedef s16 slobidx_t;
+#else
+typedef s32 slobidx_t;
+#endif
+
+/*
+ * Align struct slob_block to long for now, but can some embedded
+ * architectures get away with less?
+ */
struct slob_block {
- int units;
- struct slob_block *next;
-};
+ slobidx_t units;
+} __attribute__((aligned(sizeof(long;
typedef struct slob_block slob_t;
+/*
+ * We use struct page fields to manage some slob allocation aspects,
+ * however to avoid the horrible mess in include/linux/mm_types.h, we'll
+ * just define our own struct page type variant here.
+ */
+struct slob_page {
+ union { struct {
+ unsigned long flags;/* mandatory */
+ atomic_t _count;/* mandatory */
+ slobidx_t units;/* free units left in page */
+ unsigned long pad[2]; /* padding to avoid ptl? */
+ slob_t *free; /* pointer to first free slob block in page */
+ struct list_head list; /* linked list of free pages */
+ }; struct page page; };
+};
+static inline void struct_slob_page_wrong_size(void)
+{ BUILD_BUG_ON(sizeof(struct slob_page) != sizeof(struct page)); }
+
+/*
+ * free_slob_page: call before a slob_page is returned to the page allocator.
+ */
+static inline void free_slob_page(struct slob_page *sp)
+{
+ reset_page_mapcount(>page);
+ sp->page.mapping = NULL;
+}
+
+/*
+ * All (partially) free slob pages go on this list.
+ */
+static LIST_HEAD(free_slob_pages);
+
+/*
+ * slob_page: True for all slob pages (false for bigblock pages)
+ */
+static inline int slob_page(struct slob_page *sp)
+{
+ return test_bit(PG_active, >flags);
+}
+
+static inline void set_slob_page(struct slob_page *sp)
+{
+ __set_bit(PG_active, >flags);
+}
+
+static inline void clear_slob_page(struct slob_page *sp)
+{
+ __clear_bit(PG_active, >flags);
+}
+
+/*
+ * slob_page_free: true for pages on free_slob_pages list.
+ */
+static inline int slob_page_free(struct slob_page *sp)
+{
+ return test_bit(PG_private, >flags);
+}
+
+static inline void set_slob_page_free(struct slob_page *sp)
+{
+
[rfc][patch] slob: improvements
This patch goes on top of my previous RCU patch, and has various
improvements for slob I noticed while implementing said patch ;)
Comments?
--
Improve slob by turning the freelist into a list of pages using struct page
fields, then each page has a singly linked freelist of slob blocks via a
pointer in the struct page.
- The first benefit is that the slob freelists can be indexed by a smaller
type (2 bytes, if the PAGE_SIZE is reasonable).
- Next is that freeing is much quicker because it does not have to traverse
the entire freelist. Allocation can be slightly faster too, because we can
skip almost-full freelist pages completely.
- Slob pages are then freed immediately when they become empty, rather than
having a periodic timer try to free them. This gives efficiency and memory
consumption improvement.
Then, we don't encode seperate size and next fields into each slob block,
rather we use the sign bit to distinguish between size or next. Then
size 1 blocks contain a next offset, and others contain the size in
the first unit and next in the second unit.
- This allows minimum slob allocation alignment to go from 8 bytes to 2
bytes on 32-bit and 12 bytes to 2 bytes on 64-bit. In practice, it is
best to align them to word size, however some architectures (eg. cris)
could gain space savings from turning off this extra alignment.
Then, make kmalloc use its own slob_block at the front of the allocation
in order to encode allocation size, rather than rely on not overwriting
slob's existing header block.
- This reduces kmalloc allocation overhead similarly to alignment reductions.
- Decouples kmalloc layer from the slob allocator.
Then, add a page flag specific to slob pages.
- This means kfree of a page aligned slob block doesn't have to traverse
the bigblock list.
I would get benchmarks, but my test box's network doesn't come up with
slob before this patch. I think something is timing out. Anyway, things
are faster after the patch.
Code size goes up about 1K, however dynamic memory usage _should_ be
lower even on relatively small memory systems.
---
mm/slob.c | 271 +-
1 file changed, 200 insertions(+), 71 deletions(-)
Index: linux-2.6/mm/slob.c
===
--- linux-2.6.orig/mm/slob.c
+++ linux-2.6/mm/slob.c
@@ -34,26 +34,107 @@
#include linux/cache.h
#include linux/init.h
#include linux/module.h
-#include linux/timer.h
#include linux/rcupdate.h
+#include linux/list.h
+#include asm/atomic.h
+/*
+ * slob_block has a field 'units', which indicates size of block if +ve,
+ * or offset of next block if -ve (in SLOB_UNITs).
+ *
+ * Free blocks of size 1 unit simply contain the offset of the next block.
+ * Those with larger size contain their size in the first SLOB_UNIT of
+ * memory, and the offset of the next free block in the second SLOB_UNIT.
+ */
+#if PAGE_SIZE = (32*1024)
+typedef s16 slobidx_t;
+#else
+typedef s32 slobidx_t;
+#endif
+
+/*
+ * Align struct slob_block to long for now, but can some embedded
+ * architectures get away with less?
+ */
struct slob_block {
- int units;
- struct slob_block *next;
-};
+ slobidx_t units;
+} __attribute__((aligned(sizeof(long;
typedef struct slob_block slob_t;
+/*
+ * We use struct page fields to manage some slob allocation aspects,
+ * however to avoid the horrible mess in include/linux/mm_types.h, we'll
+ * just define our own struct page type variant here.
+ */
+struct slob_page {
+ union { struct {
+ unsigned long flags;/* mandatory */
+ atomic_t _count;/* mandatory */
+ slobidx_t units;/* free units left in page */
+ unsigned long pad[2]; /* padding to avoid ptl? */
+ slob_t *free; /* pointer to first free slob block in page */
+ struct list_head list; /* linked list of free pages */
+ }; struct page page; };
+};
+static inline void struct_slob_page_wrong_size(void)
+{ BUILD_BUG_ON(sizeof(struct slob_page) != sizeof(struct page)); }
+
+/*
+ * free_slob_page: call before a slob_page is returned to the page allocator.
+ */
+static inline void free_slob_page(struct slob_page *sp)
+{
+ reset_page_mapcount(sp-page);
+ sp-page.mapping = NULL;
+}
+
+/*
+ * All (partially) free slob pages go on this list.
+ */
+static LIST_HEAD(free_slob_pages);
+
+/*
+ * slob_page: True for all slob pages (false for bigblock pages)
+ */
+static inline int slob_page(struct slob_page *sp)
+{
+ return test_bit(PG_active, sp-flags);
+}
+
+static inline void set_slob_page(struct slob_page *sp)
+{
+ __set_bit(PG_active, sp-flags);
+}
+
+static inline void clear_slob_page(struct slob_page *sp)
+{
+ __clear_bit(PG_active, sp-flags);
+}
+
+/*
+ * slob_page_free: true for pages on free_slob_pages list.
+ */
+static inline int slob_page_free(struct slob_page *sp)
+{
+ return test_bit(PG_private,
Re: [rfc][patch] slob: improvements
On Tue, May 15, 2007 at 10:43:05AM +0200, Nick Piggin wrote:
This patch goes on top of my previous RCU patch, and has various
improvements for slob I noticed while implementing said patch ;)
Comments?
I'm warming to this. Please check that the comment block at the top is
still accurate.
+/*
+ * slob_block has a field 'units', which indicates size of block if +ve,
+ * or offset of next block if -ve (in SLOB_UNITs).
+ *
+ * Free blocks of size 1 unit simply contain the offset of the next block.
+ * Those with larger size contain their size in the first SLOB_UNIT of
+ * memory, and the offset of the next free block in the second SLOB_UNIT.
+ */
+#if PAGE_SIZE = (32*1024)
+typedef s16 slobidx_t;
+#else
+typedef s32 slobidx_t;
+#endif
This math is wrong because you're doing pointer math on slobidx_ts:
+static slob_t *slob_next(slob_t *s)
+{
+ slob_t *base = (slob_t *)((unsigned long)s PAGE_MASK);
+ slobidx_t next;
+
+ if (s[0].units 0)
+ next = -s[0].units;
+ else
+ next = s[1].units;
+ return base+next;
+}
The max is 64K.
--
Mathematics is the supreme nostalgia of our time.
-
To unsubscribe from this list: send the line unsubscribe linux-kernel in
the body of a message to [EMAIL PROTECTED]
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
Re: [rfc][patch] slob: improvements
On Tue, May 15, 2007 at 10:17:31AM -0500, Matt Mackall wrote: On Tue, May 15, 2007 at 10:43:05AM +0200, Nick Piggin wrote: This patch goes on top of my previous RCU patch, and has various improvements for slob I noticed while implementing said patch ;) Comments? I'm warming to this. Please check that the comment block at the top is still accurate. It wasn't, fixed. +/* + * slob_block has a field 'units', which indicates size of block if +ve, + * or offset of next block if -ve (in SLOB_UNITs). + * + * Free blocks of size 1 unit simply contain the offset of the next block. + * Those with larger size contain their size in the first SLOB_UNIT of + * memory, and the offset of the next free block in the second SLOB_UNIT. + */ +#if PAGE_SIZE = (32*1024) +typedef s16 slobidx_t; +#else +typedef s32 slobidx_t; +#endif This math is wrong because you're doing pointer math on slobidx_ts: It is misleading. But the max is 32K, because INT16_MAX is only 32767. Well actually, if you factor in the minimum alignment requirement, then it does indeed go up to 64K pages. Here is an updated version. --- Improve slob by turning the freelist into a list of pages using struct page fields, then each page has a singly linked freelist of slob blocks via a pointer in the struct page. - The first benefit is that the slob freelists can be indexed by a smaller type (2 bytes, if the PAGE_SIZE is reasonable). - Next is that freeing is much quicker because it does not have to traverse the entire freelist. Allocation can be slightly faster too, because we can skip almost-full freelist pages completely. - Slob pages are then freed immediately when they become empty, rather than having a periodic timer try to free them. This gives efficiency and memory consumption improvement. Then, we don't encode seperate size and next fields into each slob block, rather we use the sign bit to distinguish between size or next. Then size 1 blocks contain a next offset, and others contain the size in the first unit and next in the second unit. - This allows minimum slob allocation alignment to go from 8 bytes to 2 bytes on 32-bit and 12 bytes to 2 bytes on 64-bit. In practice, it is best to align them to word size, however some architectures (eg. cris) could gain space savings from turning off this extra alignment. Then, make kmalloc use its own slob_block at the front of the allocation in order to encode allocation size, rather than rely on not overwriting slob's existing header block. - This reduces kmalloc allocation overhead similarly to alignment reductions. - Decouples kmalloc layer from the slob allocator. Then, add a page flag specific to slob pages. - This means kfree of a page aligned slob block doesn't have to traverse the bigblock list. I would get benchmarks, but my test box's network doesn't come up with slob before this patch. I think something is timing out. Anyway, things are faster after the patch. Code size goes up about 1K, however dynamic memory usage _should_ be lower even on relatively small memory systems. Signed-off-by: Nick Piggin [EMAIL PROTECTED] --- mm/slob.c | 271 +- 1 file changed, 200 insertions(+), 71 deletions(-) Index: linux-2.6/mm/slob.c === --- linux-2.6.orig/mm/slob.c +++ linux-2.6/mm/slob.c @@ -7,53 +7,145 @@ * * The core of SLOB is a traditional KR style heap allocator, with * support for returning aligned objects. The granularity of this - * allocator is 8 bytes on x86, though it's perhaps possible to reduce - * this to 4 if it's deemed worth the effort. The slob heap is a - * singly-linked list of pages from __get_free_page, grown on demand - * and allocation from the heap is currently first-fit. + * allocator is 4 bytes on 32-bit and 8 bytes on 64-bit, though it + * could be as low as 2 if the compiler alignment requirements allow. + * + * The slob heap is a linked list of pages from __get_free_page, and + * within each page, there is a singly-linked list of free blocks (slob_t). + * The heap is grown on demand and allocation from the heap is currently + * first-fit. * * Above this is an implementation of kmalloc/kfree. Blocks returned - * from kmalloc are 8-byte aligned and prepended with a 8-byte header. + * from kmalloc are 4-byte aligned and prepended with a 4-byte header. * If kmalloc is asked for objects of PAGE_SIZE or larger, it calls * __get_free_pages directly so that it can return page-aligned blocks * and keeps a linked list of such pages and their orders. These * objects are detected in kfree() by their page alignment. * * SLAB is emulated on top of SLOB by simply calling constructors and - * destructors for every SLAB allocation. Objects are returned with - * the 8-byte alignment unless the SLAB_HWCACHE_ALIGN flag is - * set, in which case the low-level allocator will
