[Xenomai-git] Philippe Gerum : copperplate/heapobj-pshared: introduce allocation bitmap
Module: xenomai-3
Branch: wip/dovetail
Commit: 497af95d240458e758685d940d4eec6a5a9a4388
URL:
http://git.xenomai.org/?p=xenomai-3.git;a=commit;h=497af95d240458e758685d940d4eec6a5a9a4388
Author: Philippe Gerum
Date: Fri Jun 3 10:00:38 2016 +0200
copperplate/heapobj-pshared: introduce allocation bitmap
Using a free list for maintaining pages leads to pathological
execution times when releasing blocks obtained from huge heaps
(i.e. hundreds of megabytes). Rework the core to use an allocation
bitmap instead.
---
lib/copperplate/heapobj-pshared.c | 424 +
lib/copperplate/internal.h| 18 +-
2 files changed, 259 insertions(+), 183 deletions(-)
diff --git a/lib/copperplate/heapobj-pshared.c
b/lib/copperplate/heapobj-pshared.c
index 8c5dac6..bd9ea47 100644
--- a/lib/copperplate/heapobj-pshared.c
+++ b/lib/copperplate/heapobj-pshared.c
@@ -28,6 +28,7 @@
#include
#include
#include
+#include
#include
#include
#include
@@ -43,15 +44,7 @@
#include "xenomai/init.h"
#include "internal.h"
-#define HOBJ_PAGE_SHIFT9 /* 2^9 => 512 bytes */
-#define HOBJ_PAGE_SIZE (1U << HOBJ_PAGE_SHIFT)
-#define HOBJ_PAGE_MASK (~(HOBJ_PAGE_SIZE-1))
-#define HOBJ_PAGE_ALIGN(addr) (((addr)+HOBJ_PAGE_SIZE-1)&HOBJ_PAGE_MASK)
-
-#define HOBJ_MINALIGNSZ (1U << 4) /* i.e. 16 bytes */
-#define HOBJ_MAXEXTSZ (1U << 31) /* i.e. 2Gb */
-
-enum {
+enum { /* FIXME: page_free redundant with bitmap */
page_free =0,
page_cont =1,
page_list =2
@@ -66,8 +59,9 @@ struct shared_extent {
struct holder link;
memoff_t membase; /* Base offset of page array */
memoff_t memlim;/* Offset limit of page array */
- memoff_t freelist; /* Head of free page list */
- struct page_entry pagemap[1]; /* Start of page map */
+ memoff_t bitmap;/* Offset of allocation bitmap */
+ int bitwords; /* 32bit words in bitmap */
+ struct page_entry pagemap[0]; /* Start of page map */
};
/*
@@ -117,24 +111,38 @@ static inline size_t __align_to(size_t size, size_t al)
return ((size+al-1)&(~(al-1)));
}
-static inline size_t get_pagemap_size(size_t h)
+static inline size_t get_pagemap_size(size_t h,
+ memoff_t *bmapoff, int *bmapwords)
{
+ int nrpages = h >> HOBJ_PAGE_SHIFT, bitmapw;
+ size_t pagemapsz;
+
/*
* Return the size of the meta data required to map 'h' bytes
* of user memory in pages of HOBJ_PAGE_SIZE bytes. The meta
* data includes the length of the extent descriptor, plus the
-* length of the page mapping array. 'h' must be a multiple of
-* HOBJ_PAGE_SIZE on entry.
+* length of the page mapping array followed by the allocation
+* bitmap. 'h' must be a multiple of HOBJ_PAGE_SIZE on entry.
*/
assert((h & ~HOBJ_PAGE_MASK) == 0);
- return __align_to((h >> HOBJ_PAGE_SHIFT) * sizeof(struct page_entry)
- + sizeof(struct shared_extent), HOBJ_MINALIGNSZ);
+ pagemapsz = __align_to(nrpages * sizeof(struct page_entry),
+ sizeof(uint32_t));
+ bitmapw =__align_to(nrpages, 32) / 32;
+ if (bmapoff)
+ *bmapoff = offsetof(struct shared_extent, pagemap) + pagemapsz;
+ if (bmapwords)
+ *bmapwords = bitmapw;
+
+ return __align_to(pagemapsz
+ + sizeof(struct shared_extent)
+ + bitmapw * sizeof(uint32_t),
+ HOBJ_MINALIGNSZ);
}
static void init_extent(void *base, struct shared_extent *extent)
{
- caddr_t freepage;
- int n, lastpgnum;
+ int lastpgnum;
+ uint32_t *p;
__holder_init_nocheck(base, &extent->link);
@@ -146,20 +154,18 @@ static void init_extent(void *base, struct shared_extent
*extent)
*/
assert(lastpgnum >= 1);
- /* Mark each page as free in the page map. */
- for (n = 0, freepage = __shref(base, extent->membase);
-n < lastpgnum; n++, freepage += HOBJ_PAGE_SIZE) {
- *((memoff_t *)freepage) = __shoff(base, freepage) +
HOBJ_PAGE_SIZE;
- extent->pagemap[n].type = page_free;
- extent->pagemap[n].bcount = 0;
- }
-
- *((memoff_t *)freepage) = 0;
- extent->pagemap[lastpgnum].type = page_free;
- extent->pagemap[lastpgnum].bcount = 0;
+ /* Mark all pages as free in the page map. */
+ memset(extent->pagemap, 0, lastpgnum * sizeof(struct page_entry));
- /* The first page starts the free list of a new extent. */
- extent->freelist = extent->membase;
+ /* Clear the allocation bitmap. */
+ p = __shref(base, extent->bitmap);
+ memset(p, 0, extent->bitwords * sizeof(uint32_t));
+ /*
+* Mark the unused trailing bits (due to align
[Xenomai-git] Philippe Gerum : copperplate/heapobj-pshared: introduce allocation bitmap
Module: xenomai-3
Branch: wip/gpio
Commit: 75558b54e4efe3cc73b0cb040e489dd8615fb730
URL:
http://git.xenomai.org/?p=xenomai-3.git;a=commit;h=75558b54e4efe3cc73b0cb040e489dd8615fb730
Author: Philippe Gerum
Date: Fri Jun 3 10:00:38 2016 +0200
copperplate/heapobj-pshared: introduce allocation bitmap
Using a free list for maintaining pages leads to pathological
execution times when releasing blocks obtained from huge heaps
(i.e. hundreds of megabytes). Rework the core to use an allocation
bitmap instead.
---
lib/copperplate/heapobj-pshared.c | 424 +
lib/copperplate/internal.h| 18 +-
2 files changed, 259 insertions(+), 183 deletions(-)
diff --git a/lib/copperplate/heapobj-pshared.c
b/lib/copperplate/heapobj-pshared.c
index 8c5dac6..bd9ea47 100644
--- a/lib/copperplate/heapobj-pshared.c
+++ b/lib/copperplate/heapobj-pshared.c
@@ -28,6 +28,7 @@
#include
#include
#include
+#include
#include
#include
#include
@@ -43,15 +44,7 @@
#include "xenomai/init.h"
#include "internal.h"
-#define HOBJ_PAGE_SHIFT9 /* 2^9 => 512 bytes */
-#define HOBJ_PAGE_SIZE (1U << HOBJ_PAGE_SHIFT)
-#define HOBJ_PAGE_MASK (~(HOBJ_PAGE_SIZE-1))
-#define HOBJ_PAGE_ALIGN(addr) (((addr)+HOBJ_PAGE_SIZE-1)&HOBJ_PAGE_MASK)
-
-#define HOBJ_MINALIGNSZ (1U << 4) /* i.e. 16 bytes */
-#define HOBJ_MAXEXTSZ (1U << 31) /* i.e. 2Gb */
-
-enum {
+enum { /* FIXME: page_free redundant with bitmap */
page_free =0,
page_cont =1,
page_list =2
@@ -66,8 +59,9 @@ struct shared_extent {
struct holder link;
memoff_t membase; /* Base offset of page array */
memoff_t memlim;/* Offset limit of page array */
- memoff_t freelist; /* Head of free page list */
- struct page_entry pagemap[1]; /* Start of page map */
+ memoff_t bitmap;/* Offset of allocation bitmap */
+ int bitwords; /* 32bit words in bitmap */
+ struct page_entry pagemap[0]; /* Start of page map */
};
/*
@@ -117,24 +111,38 @@ static inline size_t __align_to(size_t size, size_t al)
return ((size+al-1)&(~(al-1)));
}
-static inline size_t get_pagemap_size(size_t h)
+static inline size_t get_pagemap_size(size_t h,
+ memoff_t *bmapoff, int *bmapwords)
{
+ int nrpages = h >> HOBJ_PAGE_SHIFT, bitmapw;
+ size_t pagemapsz;
+
/*
* Return the size of the meta data required to map 'h' bytes
* of user memory in pages of HOBJ_PAGE_SIZE bytes. The meta
* data includes the length of the extent descriptor, plus the
-* length of the page mapping array. 'h' must be a multiple of
-* HOBJ_PAGE_SIZE on entry.
+* length of the page mapping array followed by the allocation
+* bitmap. 'h' must be a multiple of HOBJ_PAGE_SIZE on entry.
*/
assert((h & ~HOBJ_PAGE_MASK) == 0);
- return __align_to((h >> HOBJ_PAGE_SHIFT) * sizeof(struct page_entry)
- + sizeof(struct shared_extent), HOBJ_MINALIGNSZ);
+ pagemapsz = __align_to(nrpages * sizeof(struct page_entry),
+ sizeof(uint32_t));
+ bitmapw =__align_to(nrpages, 32) / 32;
+ if (bmapoff)
+ *bmapoff = offsetof(struct shared_extent, pagemap) + pagemapsz;
+ if (bmapwords)
+ *bmapwords = bitmapw;
+
+ return __align_to(pagemapsz
+ + sizeof(struct shared_extent)
+ + bitmapw * sizeof(uint32_t),
+ HOBJ_MINALIGNSZ);
}
static void init_extent(void *base, struct shared_extent *extent)
{
- caddr_t freepage;
- int n, lastpgnum;
+ int lastpgnum;
+ uint32_t *p;
__holder_init_nocheck(base, &extent->link);
@@ -146,20 +154,18 @@ static void init_extent(void *base, struct shared_extent
*extent)
*/
assert(lastpgnum >= 1);
- /* Mark each page as free in the page map. */
- for (n = 0, freepage = __shref(base, extent->membase);
-n < lastpgnum; n++, freepage += HOBJ_PAGE_SIZE) {
- *((memoff_t *)freepage) = __shoff(base, freepage) +
HOBJ_PAGE_SIZE;
- extent->pagemap[n].type = page_free;
- extent->pagemap[n].bcount = 0;
- }
-
- *((memoff_t *)freepage) = 0;
- extent->pagemap[lastpgnum].type = page_free;
- extent->pagemap[lastpgnum].bcount = 0;
+ /* Mark all pages as free in the page map. */
+ memset(extent->pagemap, 0, lastpgnum * sizeof(struct page_entry));
- /* The first page starts the free list of a new extent. */
- extent->freelist = extent->membase;
+ /* Clear the allocation bitmap. */
+ p = __shref(base, extent->bitmap);
+ memset(p, 0, extent->bitwords * sizeof(uint32_t));
+ /*
+* Mark the unused trailing bits (due to alignment
[Xenomai-git] Philippe Gerum : copperplate/heapobj-pshared: introduce allocation bitmap
Module: xenomai-3
Branch: stable-3.0.x
Commit: 75558b54e4efe3cc73b0cb040e489dd8615fb730
URL:
http://git.xenomai.org/?p=xenomai-3.git;a=commit;h=75558b54e4efe3cc73b0cb040e489dd8615fb730
Author: Philippe Gerum
Date: Fri Jun 3 10:00:38 2016 +0200
copperplate/heapobj-pshared: introduce allocation bitmap
Using a free list for maintaining pages leads to pathological
execution times when releasing blocks obtained from huge heaps
(i.e. hundreds of megabytes). Rework the core to use an allocation
bitmap instead.
---
lib/copperplate/heapobj-pshared.c | 424 +
lib/copperplate/internal.h| 18 +-
2 files changed, 259 insertions(+), 183 deletions(-)
diff --git a/lib/copperplate/heapobj-pshared.c
b/lib/copperplate/heapobj-pshared.c
index 8c5dac6..bd9ea47 100644
--- a/lib/copperplate/heapobj-pshared.c
+++ b/lib/copperplate/heapobj-pshared.c
@@ -28,6 +28,7 @@
#include
#include
#include
+#include
#include
#include
#include
@@ -43,15 +44,7 @@
#include "xenomai/init.h"
#include "internal.h"
-#define HOBJ_PAGE_SHIFT9 /* 2^9 => 512 bytes */
-#define HOBJ_PAGE_SIZE (1U << HOBJ_PAGE_SHIFT)
-#define HOBJ_PAGE_MASK (~(HOBJ_PAGE_SIZE-1))
-#define HOBJ_PAGE_ALIGN(addr) (((addr)+HOBJ_PAGE_SIZE-1)&HOBJ_PAGE_MASK)
-
-#define HOBJ_MINALIGNSZ (1U << 4) /* i.e. 16 bytes */
-#define HOBJ_MAXEXTSZ (1U << 31) /* i.e. 2Gb */
-
-enum {
+enum { /* FIXME: page_free redundant with bitmap */
page_free =0,
page_cont =1,
page_list =2
@@ -66,8 +59,9 @@ struct shared_extent {
struct holder link;
memoff_t membase; /* Base offset of page array */
memoff_t memlim;/* Offset limit of page array */
- memoff_t freelist; /* Head of free page list */
- struct page_entry pagemap[1]; /* Start of page map */
+ memoff_t bitmap;/* Offset of allocation bitmap */
+ int bitwords; /* 32bit words in bitmap */
+ struct page_entry pagemap[0]; /* Start of page map */
};
/*
@@ -117,24 +111,38 @@ static inline size_t __align_to(size_t size, size_t al)
return ((size+al-1)&(~(al-1)));
}
-static inline size_t get_pagemap_size(size_t h)
+static inline size_t get_pagemap_size(size_t h,
+ memoff_t *bmapoff, int *bmapwords)
{
+ int nrpages = h >> HOBJ_PAGE_SHIFT, bitmapw;
+ size_t pagemapsz;
+
/*
* Return the size of the meta data required to map 'h' bytes
* of user memory in pages of HOBJ_PAGE_SIZE bytes. The meta
* data includes the length of the extent descriptor, plus the
-* length of the page mapping array. 'h' must be a multiple of
-* HOBJ_PAGE_SIZE on entry.
+* length of the page mapping array followed by the allocation
+* bitmap. 'h' must be a multiple of HOBJ_PAGE_SIZE on entry.
*/
assert((h & ~HOBJ_PAGE_MASK) == 0);
- return __align_to((h >> HOBJ_PAGE_SHIFT) * sizeof(struct page_entry)
- + sizeof(struct shared_extent), HOBJ_MINALIGNSZ);
+ pagemapsz = __align_to(nrpages * sizeof(struct page_entry),
+ sizeof(uint32_t));
+ bitmapw =__align_to(nrpages, 32) / 32;
+ if (bmapoff)
+ *bmapoff = offsetof(struct shared_extent, pagemap) + pagemapsz;
+ if (bmapwords)
+ *bmapwords = bitmapw;
+
+ return __align_to(pagemapsz
+ + sizeof(struct shared_extent)
+ + bitmapw * sizeof(uint32_t),
+ HOBJ_MINALIGNSZ);
}
static void init_extent(void *base, struct shared_extent *extent)
{
- caddr_t freepage;
- int n, lastpgnum;
+ int lastpgnum;
+ uint32_t *p;
__holder_init_nocheck(base, &extent->link);
@@ -146,20 +154,18 @@ static void init_extent(void *base, struct shared_extent
*extent)
*/
assert(lastpgnum >= 1);
- /* Mark each page as free in the page map. */
- for (n = 0, freepage = __shref(base, extent->membase);
-n < lastpgnum; n++, freepage += HOBJ_PAGE_SIZE) {
- *((memoff_t *)freepage) = __shoff(base, freepage) +
HOBJ_PAGE_SIZE;
- extent->pagemap[n].type = page_free;
- extent->pagemap[n].bcount = 0;
- }
-
- *((memoff_t *)freepage) = 0;
- extent->pagemap[lastpgnum].type = page_free;
- extent->pagemap[lastpgnum].bcount = 0;
+ /* Mark all pages as free in the page map. */
+ memset(extent->pagemap, 0, lastpgnum * sizeof(struct page_entry));
- /* The first page starts the free list of a new extent. */
- extent->freelist = extent->membase;
+ /* Clear the allocation bitmap. */
+ p = __shref(base, extent->bitmap);
+ memset(p, 0, extent->bitwords * sizeof(uint32_t));
+ /*
+* Mark the unused trailing bits (due to align
[Xenomai-git] Philippe Gerum : copperplate/heapobj-pshared: introduce allocation bitmap
Module: xenomai-3
Branch: next
Commit: 497af95d240458e758685d940d4eec6a5a9a4388
URL:
http://git.xenomai.org/?p=xenomai-3.git;a=commit;h=497af95d240458e758685d940d4eec6a5a9a4388
Author: Philippe Gerum
Date: Fri Jun 3 10:00:38 2016 +0200
copperplate/heapobj-pshared: introduce allocation bitmap
Using a free list for maintaining pages leads to pathological
execution times when releasing blocks obtained from huge heaps
(i.e. hundreds of megabytes). Rework the core to use an allocation
bitmap instead.
---
lib/copperplate/heapobj-pshared.c | 424 +
lib/copperplate/internal.h| 18 +-
2 files changed, 259 insertions(+), 183 deletions(-)
diff --git a/lib/copperplate/heapobj-pshared.c
b/lib/copperplate/heapobj-pshared.c
index 8c5dac6..bd9ea47 100644
--- a/lib/copperplate/heapobj-pshared.c
+++ b/lib/copperplate/heapobj-pshared.c
@@ -28,6 +28,7 @@
#include
#include
#include
+#include
#include
#include
#include
@@ -43,15 +44,7 @@
#include "xenomai/init.h"
#include "internal.h"
-#define HOBJ_PAGE_SHIFT9 /* 2^9 => 512 bytes */
-#define HOBJ_PAGE_SIZE (1U << HOBJ_PAGE_SHIFT)
-#define HOBJ_PAGE_MASK (~(HOBJ_PAGE_SIZE-1))
-#define HOBJ_PAGE_ALIGN(addr) (((addr)+HOBJ_PAGE_SIZE-1)&HOBJ_PAGE_MASK)
-
-#define HOBJ_MINALIGNSZ (1U << 4) /* i.e. 16 bytes */
-#define HOBJ_MAXEXTSZ (1U << 31) /* i.e. 2Gb */
-
-enum {
+enum { /* FIXME: page_free redundant with bitmap */
page_free =0,
page_cont =1,
page_list =2
@@ -66,8 +59,9 @@ struct shared_extent {
struct holder link;
memoff_t membase; /* Base offset of page array */
memoff_t memlim;/* Offset limit of page array */
- memoff_t freelist; /* Head of free page list */
- struct page_entry pagemap[1]; /* Start of page map */
+ memoff_t bitmap;/* Offset of allocation bitmap */
+ int bitwords; /* 32bit words in bitmap */
+ struct page_entry pagemap[0]; /* Start of page map */
};
/*
@@ -117,24 +111,38 @@ static inline size_t __align_to(size_t size, size_t al)
return ((size+al-1)&(~(al-1)));
}
-static inline size_t get_pagemap_size(size_t h)
+static inline size_t get_pagemap_size(size_t h,
+ memoff_t *bmapoff, int *bmapwords)
{
+ int nrpages = h >> HOBJ_PAGE_SHIFT, bitmapw;
+ size_t pagemapsz;
+
/*
* Return the size of the meta data required to map 'h' bytes
* of user memory in pages of HOBJ_PAGE_SIZE bytes. The meta
* data includes the length of the extent descriptor, plus the
-* length of the page mapping array. 'h' must be a multiple of
-* HOBJ_PAGE_SIZE on entry.
+* length of the page mapping array followed by the allocation
+* bitmap. 'h' must be a multiple of HOBJ_PAGE_SIZE on entry.
*/
assert((h & ~HOBJ_PAGE_MASK) == 0);
- return __align_to((h >> HOBJ_PAGE_SHIFT) * sizeof(struct page_entry)
- + sizeof(struct shared_extent), HOBJ_MINALIGNSZ);
+ pagemapsz = __align_to(nrpages * sizeof(struct page_entry),
+ sizeof(uint32_t));
+ bitmapw =__align_to(nrpages, 32) / 32;
+ if (bmapoff)
+ *bmapoff = offsetof(struct shared_extent, pagemap) + pagemapsz;
+ if (bmapwords)
+ *bmapwords = bitmapw;
+
+ return __align_to(pagemapsz
+ + sizeof(struct shared_extent)
+ + bitmapw * sizeof(uint32_t),
+ HOBJ_MINALIGNSZ);
}
static void init_extent(void *base, struct shared_extent *extent)
{
- caddr_t freepage;
- int n, lastpgnum;
+ int lastpgnum;
+ uint32_t *p;
__holder_init_nocheck(base, &extent->link);
@@ -146,20 +154,18 @@ static void init_extent(void *base, struct shared_extent
*extent)
*/
assert(lastpgnum >= 1);
- /* Mark each page as free in the page map. */
- for (n = 0, freepage = __shref(base, extent->membase);
-n < lastpgnum; n++, freepage += HOBJ_PAGE_SIZE) {
- *((memoff_t *)freepage) = __shoff(base, freepage) +
HOBJ_PAGE_SIZE;
- extent->pagemap[n].type = page_free;
- extent->pagemap[n].bcount = 0;
- }
-
- *((memoff_t *)freepage) = 0;
- extent->pagemap[lastpgnum].type = page_free;
- extent->pagemap[lastpgnum].bcount = 0;
+ /* Mark all pages as free in the page map. */
+ memset(extent->pagemap, 0, lastpgnum * sizeof(struct page_entry));
- /* The first page starts the free list of a new extent. */
- extent->freelist = extent->membase;
+ /* Clear the allocation bitmap. */
+ p = __shref(base, extent->bitmap);
+ memset(p, 0, extent->bitwords * sizeof(uint32_t));
+ /*
+* Mark the unused trailing bits (due to alignment) as
[Xenomai-git] Philippe Gerum : copperplate/heapobj-pshared: introduce allocation bitmap
Module: xenomai-3
Branch: wip/heap-bitmap
Commit: f36e50b95dcc5a897bb8685eefb4a4077407cc66
URL:
http://git.xenomai.org/?p=xenomai-3.git;a=commit;h=f36e50b95dcc5a897bb8685eefb4a4077407cc66
Author: Philippe Gerum
Date: Fri Jun 3 10:00:38 2016 +0200
copperplate/heapobj-pshared: introduce allocation bitmap
Using a free list for maintaining pages leads to pathological
execution times when releasing blocks obtained from huge heaps
(i.e. hundreds of megabytes). Rework the core to use an allocation
bitmap instead.
---
lib/copperplate/heapobj-pshared.c | 424 +
lib/copperplate/internal.h| 18 +-
2 files changed, 259 insertions(+), 183 deletions(-)
diff --git a/lib/copperplate/heapobj-pshared.c
b/lib/copperplate/heapobj-pshared.c
index 8c5dac6..bd9ea47 100644
--- a/lib/copperplate/heapobj-pshared.c
+++ b/lib/copperplate/heapobj-pshared.c
@@ -28,6 +28,7 @@
#include
#include
#include
+#include
#include
#include
#include
@@ -43,15 +44,7 @@
#include "xenomai/init.h"
#include "internal.h"
-#define HOBJ_PAGE_SHIFT9 /* 2^9 => 512 bytes */
-#define HOBJ_PAGE_SIZE (1U << HOBJ_PAGE_SHIFT)
-#define HOBJ_PAGE_MASK (~(HOBJ_PAGE_SIZE-1))
-#define HOBJ_PAGE_ALIGN(addr) (((addr)+HOBJ_PAGE_SIZE-1)&HOBJ_PAGE_MASK)
-
-#define HOBJ_MINALIGNSZ (1U << 4) /* i.e. 16 bytes */
-#define HOBJ_MAXEXTSZ (1U << 31) /* i.e. 2Gb */
-
-enum {
+enum { /* FIXME: page_free redundant with bitmap */
page_free =0,
page_cont =1,
page_list =2
@@ -66,8 +59,9 @@ struct shared_extent {
struct holder link;
memoff_t membase; /* Base offset of page array */
memoff_t memlim;/* Offset limit of page array */
- memoff_t freelist; /* Head of free page list */
- struct page_entry pagemap[1]; /* Start of page map */
+ memoff_t bitmap;/* Offset of allocation bitmap */
+ int bitwords; /* 32bit words in bitmap */
+ struct page_entry pagemap[0]; /* Start of page map */
};
/*
@@ -117,24 +111,38 @@ static inline size_t __align_to(size_t size, size_t al)
return ((size+al-1)&(~(al-1)));
}
-static inline size_t get_pagemap_size(size_t h)
+static inline size_t get_pagemap_size(size_t h,
+ memoff_t *bmapoff, int *bmapwords)
{
+ int nrpages = h >> HOBJ_PAGE_SHIFT, bitmapw;
+ size_t pagemapsz;
+
/*
* Return the size of the meta data required to map 'h' bytes
* of user memory in pages of HOBJ_PAGE_SIZE bytes. The meta
* data includes the length of the extent descriptor, plus the
-* length of the page mapping array. 'h' must be a multiple of
-* HOBJ_PAGE_SIZE on entry.
+* length of the page mapping array followed by the allocation
+* bitmap. 'h' must be a multiple of HOBJ_PAGE_SIZE on entry.
*/
assert((h & ~HOBJ_PAGE_MASK) == 0);
- return __align_to((h >> HOBJ_PAGE_SHIFT) * sizeof(struct page_entry)
- + sizeof(struct shared_extent), HOBJ_MINALIGNSZ);
+ pagemapsz = __align_to(nrpages * sizeof(struct page_entry),
+ sizeof(uint32_t));
+ bitmapw =__align_to(nrpages, 32) / 32;
+ if (bmapoff)
+ *bmapoff = offsetof(struct shared_extent, pagemap) + pagemapsz;
+ if (bmapwords)
+ *bmapwords = bitmapw;
+
+ return __align_to(pagemapsz
+ + sizeof(struct shared_extent)
+ + bitmapw * sizeof(uint32_t),
+ HOBJ_MINALIGNSZ);
}
static void init_extent(void *base, struct shared_extent *extent)
{
- caddr_t freepage;
- int n, lastpgnum;
+ int lastpgnum;
+ uint32_t *p;
__holder_init_nocheck(base, &extent->link);
@@ -146,20 +154,18 @@ static void init_extent(void *base, struct shared_extent
*extent)
*/
assert(lastpgnum >= 1);
- /* Mark each page as free in the page map. */
- for (n = 0, freepage = __shref(base, extent->membase);
-n < lastpgnum; n++, freepage += HOBJ_PAGE_SIZE) {
- *((memoff_t *)freepage) = __shoff(base, freepage) +
HOBJ_PAGE_SIZE;
- extent->pagemap[n].type = page_free;
- extent->pagemap[n].bcount = 0;
- }
-
- *((memoff_t *)freepage) = 0;
- extent->pagemap[lastpgnum].type = page_free;
- extent->pagemap[lastpgnum].bcount = 0;
+ /* Mark all pages as free in the page map. */
+ memset(extent->pagemap, 0, lastpgnum * sizeof(struct page_entry));
- /* The first page starts the free list of a new extent. */
- extent->freelist = extent->membase;
+ /* Clear the allocation bitmap. */
+ p = __shref(base, extent->bitmap);
+ memset(p, 0, extent->bitwords * sizeof(uint32_t));
+ /*
+* Mark the unused trailing bits (due to al
[Xenomai-git] Philippe Gerum : copperplate/heapobj-pshared: introduce allocation bitmap
Module: xenomai-3
Branch: wip/heap-bitmap
Commit: 1a01fe305302af8e1cfabb32bd5c0e60ac4f6d46
URL:
http://git.xenomai.org/?p=xenomai-3.git;a=commit;h=1a01fe305302af8e1cfabb32bd5c0e60ac4f6d46
Author: Philippe Gerum
Date: Fri Jun 3 10:00:38 2016 +0200
copperplate/heapobj-pshared: introduce allocation bitmap
Using a free list for maintaining pages leads to pathological
execution times when releasing blocks obtained from huge heaps
(i.e. hundreds of megabytes). Rework the core to use an allocation
bitmap instead.
---
lib/copperplate/heapobj-pshared.c | 418 +
lib/copperplate/internal.h| 18 +-
2 files changed, 253 insertions(+), 183 deletions(-)
diff --git a/lib/copperplate/heapobj-pshared.c
b/lib/copperplate/heapobj-pshared.c
index 8c5dac6..c897d69 100644
--- a/lib/copperplate/heapobj-pshared.c
+++ b/lib/copperplate/heapobj-pshared.c
@@ -28,6 +28,7 @@
#include
#include
#include
+#include
#include
#include
#include
@@ -43,15 +44,7 @@
#include "xenomai/init.h"
#include "internal.h"
-#define HOBJ_PAGE_SHIFT9 /* 2^9 => 512 bytes */
-#define HOBJ_PAGE_SIZE (1U << HOBJ_PAGE_SHIFT)
-#define HOBJ_PAGE_MASK (~(HOBJ_PAGE_SIZE-1))
-#define HOBJ_PAGE_ALIGN(addr) (((addr)+HOBJ_PAGE_SIZE-1)&HOBJ_PAGE_MASK)
-
-#define HOBJ_MINALIGNSZ (1U << 4) /* i.e. 16 bytes */
-#define HOBJ_MAXEXTSZ (1U << 31) /* i.e. 2Gb */
-
-enum {
+enum { /* FIXME: page_free redundant with bitmap */
page_free =0,
page_cont =1,
page_list =2
@@ -66,8 +59,9 @@ struct shared_extent {
struct holder link;
memoff_t membase; /* Base offset of page array */
memoff_t memlim;/* Offset limit of page array */
- memoff_t freelist; /* Head of free page list */
- struct page_entry pagemap[1]; /* Start of page map */
+ memoff_t bitmap;/* Offset of allocation bitmap */
+ int bitwords; /* 32bit words in bitmap */
+ struct page_entry pagemap[0]; /* Start of page map */
};
/*
@@ -117,24 +111,38 @@ static inline size_t __align_to(size_t size, size_t al)
return ((size+al-1)&(~(al-1)));
}
-static inline size_t get_pagemap_size(size_t h)
+static inline size_t get_pagemap_size(size_t h,
+ memoff_t *bmapoff, int *bmapwords)
{
+ int nrpages = h >> HOBJ_PAGE_SHIFT, bitmapw;
+ size_t pagemapsz;
+
/*
* Return the size of the meta data required to map 'h' bytes
* of user memory in pages of HOBJ_PAGE_SIZE bytes. The meta
* data includes the length of the extent descriptor, plus the
-* length of the page mapping array. 'h' must be a multiple of
-* HOBJ_PAGE_SIZE on entry.
+* length of the page mapping array followed by the allocation
+* bitmap. 'h' must be a multiple of HOBJ_PAGE_SIZE on entry.
*/
assert((h & ~HOBJ_PAGE_MASK) == 0);
- return __align_to((h >> HOBJ_PAGE_SHIFT) * sizeof(struct page_entry)
- + sizeof(struct shared_extent), HOBJ_MINALIGNSZ);
+ pagemapsz = __align_to(nrpages * sizeof(struct page_entry),
+ sizeof(uint32_t));
+ bitmapw =__align_to(nrpages, 32) / 32;
+ if (bmapoff)
+ *bmapoff = offsetof(struct shared_extent, pagemap) + pagemapsz;
+ if (bmapwords)
+ *bmapwords = bitmapw;
+
+ return __align_to(pagemapsz
+ + sizeof(struct shared_extent)
+ + bitmapw * sizeof(uint32_t),
+ HOBJ_MINALIGNSZ);
}
static void init_extent(void *base, struct shared_extent *extent)
{
- caddr_t freepage;
- int n, lastpgnum;
+ int lastpgnum;
+ uint32_t *p;
__holder_init_nocheck(base, &extent->link);
@@ -146,20 +154,18 @@ static void init_extent(void *base, struct shared_extent
*extent)
*/
assert(lastpgnum >= 1);
- /* Mark each page as free in the page map. */
- for (n = 0, freepage = __shref(base, extent->membase);
-n < lastpgnum; n++, freepage += HOBJ_PAGE_SIZE) {
- *((memoff_t *)freepage) = __shoff(base, freepage) +
HOBJ_PAGE_SIZE;
- extent->pagemap[n].type = page_free;
- extent->pagemap[n].bcount = 0;
- }
-
- *((memoff_t *)freepage) = 0;
- extent->pagemap[lastpgnum].type = page_free;
- extent->pagemap[lastpgnum].bcount = 0;
+ /* Mark all pages as free in the page map. */
+ memset(extent->pagemap, 0, lastpgnum * sizeof(struct page_entry));
- /* The first page starts the free list of a new extent. */
- extent->freelist = extent->membase;
+ /* Clear the allocation bitmap. */
+ p = __shref(base, extent->bitmap);
+ memset(p, 0, extent->bitwords * sizeof(uint32_t));
+ /*
+* Mark the unused trailing bits (due to al
[Xenomai-git] Philippe Gerum : copperplate/heapobj-pshared: introduce allocation bitmap
Module: xenomai-3
Branch: wip/heap-bitmap
Commit: 5f317e3756a92bfbb86da0f46826da9fe626bc2d
URL:
http://git.xenomai.org/?p=xenomai-3.git;a=commit;h=5f317e3756a92bfbb86da0f46826da9fe626bc2d
Author: Philippe Gerum
Date: Fri Jun 3 10:00:38 2016 +0200
copperplate/heapobj-pshared: introduce allocation bitmap
Using a free list for maintaining pages leads to pathological
execution times when releasing blocks obtained from huge heaps
(i.e. hundreds of megabytes). Rework the core to use an allocation
bitmap instead.
---
lib/copperplate/heapobj-pshared.c | 411 +
lib/copperplate/internal.h| 18 +-
2 files changed, 251 insertions(+), 178 deletions(-)
diff --git a/lib/copperplate/heapobj-pshared.c
b/lib/copperplate/heapobj-pshared.c
index 8c5dac6..43aac70 100644
--- a/lib/copperplate/heapobj-pshared.c
+++ b/lib/copperplate/heapobj-pshared.c
@@ -28,6 +28,7 @@
#include
#include
#include
+#include
#include
#include
#include
@@ -43,15 +44,7 @@
#include "xenomai/init.h"
#include "internal.h"
-#define HOBJ_PAGE_SHIFT9 /* 2^9 => 512 bytes */
-#define HOBJ_PAGE_SIZE (1U << HOBJ_PAGE_SHIFT)
-#define HOBJ_PAGE_MASK (~(HOBJ_PAGE_SIZE-1))
-#define HOBJ_PAGE_ALIGN(addr) (((addr)+HOBJ_PAGE_SIZE-1)&HOBJ_PAGE_MASK)
-
-#define HOBJ_MINALIGNSZ (1U << 4) /* i.e. 16 bytes */
-#define HOBJ_MAXEXTSZ (1U << 31) /* i.e. 2Gb */
-
-enum {
+enum { /* FIXME: page_free redundant with future
bitmap */
page_free =0,
page_cont =1,
page_list =2
@@ -66,8 +59,9 @@ struct shared_extent {
struct holder link;
memoff_t membase; /* Base offset of page array */
memoff_t memlim;/* Offset limit of page array */
- memoff_t freelist; /* Head of free page list */
- struct page_entry pagemap[1]; /* Start of page map */
+ memoff_t bitmap;/* Offset of allocation bitmap */
+ int bitwords; /* 32bit words in bitmap */
+ struct page_entry pagemap[0]; /* Start of page map */
};
/*
@@ -117,24 +111,38 @@ static inline size_t __align_to(size_t size, size_t al)
return ((size+al-1)&(~(al-1)));
}
-static inline size_t get_pagemap_size(size_t h)
+static inline size_t get_pagemap_size(size_t h,
+ memoff_t *bmapoff, int *bmapwords)
{
+ int nrpages = h >> HOBJ_PAGE_SHIFT, bitmapw;
+ size_t pagemapsz;
+
/*
* Return the size of the meta data required to map 'h' bytes
* of user memory in pages of HOBJ_PAGE_SIZE bytes. The meta
* data includes the length of the extent descriptor, plus the
-* length of the page mapping array. 'h' must be a multiple of
-* HOBJ_PAGE_SIZE on entry.
+* length of the page mapping array followed by the allocation
+* bitmap. 'h' must be a multiple of HOBJ_PAGE_SIZE on entry.
*/
assert((h & ~HOBJ_PAGE_MASK) == 0);
- return __align_to((h >> HOBJ_PAGE_SHIFT) * sizeof(struct page_entry)
- + sizeof(struct shared_extent), HOBJ_MINALIGNSZ);
+ pagemapsz = __align_to(nrpages * sizeof(struct page_entry),
+ sizeof(uint32_t));
+ bitmapw =__align_to(nrpages, 32) / 32;
+ if (bmapoff)
+ *bmapoff = offsetof(struct shared_extent, pagemap) + pagemapsz;
+ if (bmapwords)
+ *bmapwords = bitmapw;
+
+ return __align_to(pagemapsz
+ + sizeof(struct shared_extent)
+ + bitmapw * sizeof(uint32_t),
+ HOBJ_MINALIGNSZ);
}
static void init_extent(void *base, struct shared_extent *extent)
{
- caddr_t freepage;
int n, lastpgnum;
+ uint32_t *p;
__holder_init_nocheck(base, &extent->link);
@@ -147,19 +155,20 @@ static void init_extent(void *base, struct shared_extent
*extent)
assert(lastpgnum >= 1);
/* Mark each page as free in the page map. */
- for (n = 0, freepage = __shref(base, extent->membase);
-n < lastpgnum; n++, freepage += HOBJ_PAGE_SIZE) {
- *((memoff_t *)freepage) = __shoff(base, freepage) +
HOBJ_PAGE_SIZE;
+ for (n = 0; n <= lastpgnum; n++) {
extent->pagemap[n].type = page_free;
extent->pagemap[n].bcount = 0;
}
- *((memoff_t *)freepage) = 0;
- extent->pagemap[lastpgnum].type = page_free;
- extent->pagemap[lastpgnum].bcount = 0;
-
- /* The first page starts the free list of a new extent. */
- extent->freelist = extent->membase;
+ /* Clear the allocation bitmap. */
+ p = __shref(base, extent->bitmap);
+ memset(p, 0, extent->bitwords * sizeof(uint32_t));
+ /*
+* Mark the unused trailing bits (due to alignment) as busy,
+* we don't want to pick them since they don't map any actual
+* memory from th
[Xenomai-git] Philippe Gerum : copperplate/heapobj-pshared: introduce allocation bitmap
Module: xenomai-3
Branch: wip/heap-bitmap
Commit: 4b6c4cce7debb28937ae914c12b89c5a68db11cd
URL:
http://git.xenomai.org/?p=xenomai-3.git;a=commit;h=4b6c4cce7debb28937ae914c12b89c5a68db11cd
Author: Philippe Gerum
Date: Fri Jun 3 10:00:38 2016 +0200
copperplate/heapobj-pshared: introduce allocation bitmap
Using a free list leads to pathological execution times when releasing
blocks obtained from huge heaps (i.e. hundreds of megabytes). Rework
the core to use an allocation bitmap instead.
---
lib/copperplate/heapobj-pshared.c | 411 +
lib/copperplate/internal.h| 18 +-
2 files changed, 251 insertions(+), 178 deletions(-)
diff --git a/lib/copperplate/heapobj-pshared.c
b/lib/copperplate/heapobj-pshared.c
index 8c5dac6..43aac70 100644
--- a/lib/copperplate/heapobj-pshared.c
+++ b/lib/copperplate/heapobj-pshared.c
@@ -28,6 +28,7 @@
#include
#include
#include
+#include
#include
#include
#include
@@ -43,15 +44,7 @@
#include "xenomai/init.h"
#include "internal.h"
-#define HOBJ_PAGE_SHIFT9 /* 2^9 => 512 bytes */
-#define HOBJ_PAGE_SIZE (1U << HOBJ_PAGE_SHIFT)
-#define HOBJ_PAGE_MASK (~(HOBJ_PAGE_SIZE-1))
-#define HOBJ_PAGE_ALIGN(addr) (((addr)+HOBJ_PAGE_SIZE-1)&HOBJ_PAGE_MASK)
-
-#define HOBJ_MINALIGNSZ (1U << 4) /* i.e. 16 bytes */
-#define HOBJ_MAXEXTSZ (1U << 31) /* i.e. 2Gb */
-
-enum {
+enum { /* FIXME: page_free redundant with future
bitmap */
page_free =0,
page_cont =1,
page_list =2
@@ -66,8 +59,9 @@ struct shared_extent {
struct holder link;
memoff_t membase; /* Base offset of page array */
memoff_t memlim;/* Offset limit of page array */
- memoff_t freelist; /* Head of free page list */
- struct page_entry pagemap[1]; /* Start of page map */
+ memoff_t bitmap;/* Offset of allocation bitmap */
+ int bitwords; /* 32bit words in bitmap */
+ struct page_entry pagemap[0]; /* Start of page map */
};
/*
@@ -117,24 +111,38 @@ static inline size_t __align_to(size_t size, size_t al)
return ((size+al-1)&(~(al-1)));
}
-static inline size_t get_pagemap_size(size_t h)
+static inline size_t get_pagemap_size(size_t h,
+ memoff_t *bmapoff, int *bmapwords)
{
+ int nrpages = h >> HOBJ_PAGE_SHIFT, bitmapw;
+ size_t pagemapsz;
+
/*
* Return the size of the meta data required to map 'h' bytes
* of user memory in pages of HOBJ_PAGE_SIZE bytes. The meta
* data includes the length of the extent descriptor, plus the
-* length of the page mapping array. 'h' must be a multiple of
-* HOBJ_PAGE_SIZE on entry.
+* length of the page mapping array followed by the allocation
+* bitmap. 'h' must be a multiple of HOBJ_PAGE_SIZE on entry.
*/
assert((h & ~HOBJ_PAGE_MASK) == 0);
- return __align_to((h >> HOBJ_PAGE_SHIFT) * sizeof(struct page_entry)
- + sizeof(struct shared_extent), HOBJ_MINALIGNSZ);
+ pagemapsz = __align_to(nrpages * sizeof(struct page_entry),
+ sizeof(uint32_t));
+ bitmapw =__align_to(nrpages, 32) / 32;
+ if (bmapoff)
+ *bmapoff = offsetof(struct shared_extent, pagemap) + pagemapsz;
+ if (bmapwords)
+ *bmapwords = bitmapw;
+
+ return __align_to(pagemapsz
+ + sizeof(struct shared_extent)
+ + bitmapw * sizeof(uint32_t),
+ HOBJ_MINALIGNSZ);
}
static void init_extent(void *base, struct shared_extent *extent)
{
- caddr_t freepage;
int n, lastpgnum;
+ uint32_t *p;
__holder_init_nocheck(base, &extent->link);
@@ -147,19 +155,20 @@ static void init_extent(void *base, struct shared_extent
*extent)
assert(lastpgnum >= 1);
/* Mark each page as free in the page map. */
- for (n = 0, freepage = __shref(base, extent->membase);
-n < lastpgnum; n++, freepage += HOBJ_PAGE_SIZE) {
- *((memoff_t *)freepage) = __shoff(base, freepage) +
HOBJ_PAGE_SIZE;
+ for (n = 0; n <= lastpgnum; n++) {
extent->pagemap[n].type = page_free;
extent->pagemap[n].bcount = 0;
}
- *((memoff_t *)freepage) = 0;
- extent->pagemap[lastpgnum].type = page_free;
- extent->pagemap[lastpgnum].bcount = 0;
-
- /* The first page starts the free list of a new extent. */
- extent->freelist = extent->membase;
+ /* Clear the allocation bitmap. */
+ p = __shref(base, extent->bitmap);
+ memset(p, 0, extent->bitwords * sizeof(uint32_t));
+ /*
+* Mark the unused trailing bits (due to alignment) as busy,
+* we don't want to pick them since they don't map any actual
+* memory from the page pool.
+
[Xenomai-git] Philippe Gerum : copperplate/heapobj-pshared: introduce allocation bitmap
Module: xenomai-3
Branch: wip/heap-bitmap
Commit: 8f3d0b1a0aac47b7b2a5f1b3b6e307a2aab9643c
URL:
http://git.xenomai.org/?p=xenomai-3.git;a=commit;h=8f3d0b1a0aac47b7b2a5f1b3b6e307a2aab9643c
Author: Philippe Gerum
Date: Fri Jun 3 10:00:38 2016 +0200
copperplate/heapobj-pshared: introduce allocation bitmap
Using a free list leads to pathological execution times when releasing
blocks obtained from huge heaps (i.e. hundreds of megabytes). Rework
the core to use an allocation bitmap instead.
---
lib/copperplate/heapobj-pshared.c | 411 +
lib/copperplate/internal.h| 18 +-
2 files changed, 251 insertions(+), 178 deletions(-)
diff --git a/lib/copperplate/heapobj-pshared.c
b/lib/copperplate/heapobj-pshared.c
index 8c5dac6..8b8156b 100644
--- a/lib/copperplate/heapobj-pshared.c
+++ b/lib/copperplate/heapobj-pshared.c
@@ -28,6 +28,7 @@
#include
#include
#include
+#include
#include
#include
#include
@@ -43,15 +44,7 @@
#include "xenomai/init.h"
#include "internal.h"
-#define HOBJ_PAGE_SHIFT9 /* 2^9 => 512 bytes */
-#define HOBJ_PAGE_SIZE (1U << HOBJ_PAGE_SHIFT)
-#define HOBJ_PAGE_MASK (~(HOBJ_PAGE_SIZE-1))
-#define HOBJ_PAGE_ALIGN(addr) (((addr)+HOBJ_PAGE_SIZE-1)&HOBJ_PAGE_MASK)
-
-#define HOBJ_MINALIGNSZ (1U << 4) /* i.e. 16 bytes */
-#define HOBJ_MAXEXTSZ (1U << 31) /* i.e. 2Gb */
-
-enum {
+enum { /* FIXME: page_free redundant with future
bitmap */
page_free =0,
page_cont =1,
page_list =2
@@ -66,8 +59,9 @@ struct shared_extent {
struct holder link;
memoff_t membase; /* Base offset of page array */
memoff_t memlim;/* Offset limit of page array */
- memoff_t freelist; /* Head of free page list */
- struct page_entry pagemap[1]; /* Start of page map */
+ memoff_t bitmap;/* Offset of allocation bitmap */
+ int bitwords; /* 32bit words in bitmap */
+ struct page_entry pagemap[0]; /* Start of page map */
};
/*
@@ -117,24 +111,38 @@ static inline size_t __align_to(size_t size, size_t al)
return ((size+al-1)&(~(al-1)));
}
-static inline size_t get_pagemap_size(size_t h)
+static inline size_t get_pagemap_size(size_t h,
+ memoff_t *bmapoff, int *bmapwords)
{
+ int nrpages = h >> HOBJ_PAGE_SHIFT, bitmapw;
+ size_t pagemapsz;
+
/*
* Return the size of the meta data required to map 'h' bytes
* of user memory in pages of HOBJ_PAGE_SIZE bytes. The meta
* data includes the length of the extent descriptor, plus the
-* length of the page mapping array. 'h' must be a multiple of
-* HOBJ_PAGE_SIZE on entry.
+* length of the page mapping array followed by the allocation
+* bitmap. 'h' must be a multiple of HOBJ_PAGE_SIZE on entry.
*/
assert((h & ~HOBJ_PAGE_MASK) == 0);
- return __align_to((h >> HOBJ_PAGE_SHIFT) * sizeof(struct page_entry)
- + sizeof(struct shared_extent), HOBJ_MINALIGNSZ);
+ pagemapsz = __align_to(nrpages * sizeof(struct page_entry),
+ sizeof(uint32_t));
+ bitmapw =__align_to(nrpages, 32) / 32;
+ if (bmapoff)
+ *bmapoff = offsetof(struct shared_extent, pagemap) + pagemapsz;
+ if (bmapwords)
+ *bmapwords = bitmapw;
+
+ return __align_to(pagemapsz
+ + sizeof(struct shared_extent)
+ + bitmapw * sizeof(uint32_t),
+ HOBJ_MINALIGNSZ);
}
static void init_extent(void *base, struct shared_extent *extent)
{
- caddr_t freepage;
int n, lastpgnum;
+ uint32_t *p;
__holder_init_nocheck(base, &extent->link);
@@ -147,19 +155,20 @@ static void init_extent(void *base, struct shared_extent
*extent)
assert(lastpgnum >= 1);
/* Mark each page as free in the page map. */
- for (n = 0, freepage = __shref(base, extent->membase);
-n < lastpgnum; n++, freepage += HOBJ_PAGE_SIZE) {
- *((memoff_t *)freepage) = __shoff(base, freepage) +
HOBJ_PAGE_SIZE;
+ for (n = 0; n <= lastpgnum; n++) {
extent->pagemap[n].type = page_free;
extent->pagemap[n].bcount = 0;
}
- *((memoff_t *)freepage) = 0;
- extent->pagemap[lastpgnum].type = page_free;
- extent->pagemap[lastpgnum].bcount = 0;
-
- /* The first page starts the free list of a new extent. */
- extent->freelist = extent->membase;
+ /* Clear the allocation bitmap. */
+ p = __shref(base, extent->bitmap);
+ memset(p, 0, extent->bitwords * sizeof(uint32_t));
+ /*
+* Mark the unused trailing bits (due to alignment) as busy,
+* we don't want to pick them since they don't map any actual
+* memory from the page pool.
+
[Xenomai-git] Philippe Gerum : copperplate/heapobj-pshared: introduce allocation bitmap
Module: xenomai-3
Branch: wip/heap-bitmap
Commit: 92650808fc2c3f19248a81987f1d327affbbb152
URL:
http://git.xenomai.org/?p=xenomai-3.git;a=commit;h=92650808fc2c3f19248a81987f1d327affbbb152
Author: Philippe Gerum
Date: Fri Jun 3 10:00:38 2016 +0200
copperplate/heapobj-pshared: introduce allocation bitmap
Using a free list leads to pathological execution times when releasing
blocks obtained from huge heaps (i.e. hundreds of megabytes). Rework
the core to use an allocation bitmap instead.
---
lib/copperplate/heapobj-pshared.c | 389 +
lib/copperplate/internal.h| 18 +-
2 files changed, 238 insertions(+), 169 deletions(-)
diff --git a/lib/copperplate/heapobj-pshared.c
b/lib/copperplate/heapobj-pshared.c
index 8c5dac6..557c540 100644
--- a/lib/copperplate/heapobj-pshared.c
+++ b/lib/copperplate/heapobj-pshared.c
@@ -28,6 +28,7 @@
#include
#include
#include
+#include
#include
#include
#include
@@ -43,15 +44,7 @@
#include "xenomai/init.h"
#include "internal.h"
-#define HOBJ_PAGE_SHIFT9 /* 2^9 => 512 bytes */
-#define HOBJ_PAGE_SIZE (1U << HOBJ_PAGE_SHIFT)
-#define HOBJ_PAGE_MASK (~(HOBJ_PAGE_SIZE-1))
-#define HOBJ_PAGE_ALIGN(addr) (((addr)+HOBJ_PAGE_SIZE-1)&HOBJ_PAGE_MASK)
-
-#define HOBJ_MINALIGNSZ (1U << 4) /* i.e. 16 bytes */
-#define HOBJ_MAXEXTSZ (1U << 31) /* i.e. 2Gb */
-
-enum {
+enum { /* FIXME: page_free redundant with future
bitmap */
page_free =0,
page_cont =1,
page_list =2
@@ -66,8 +59,9 @@ struct shared_extent {
struct holder link;
memoff_t membase; /* Base offset of page array */
memoff_t memlim;/* Offset limit of page array */
- memoff_t freelist; /* Head of free page list */
- struct page_entry pagemap[1]; /* Start of page map */
+ memoff_t bitmap;/* Offset of allocation bitmap */
+ int bitwords; /* 32bit words in bitmap */
+ struct page_entry pagemap[0]; /* Start of page map */
};
/*
@@ -117,24 +111,38 @@ static inline size_t __align_to(size_t size, size_t al)
return ((size+al-1)&(~(al-1)));
}
-static inline size_t get_pagemap_size(size_t h)
+static inline size_t get_pagemap_size(size_t h,
+ memoff_t *bmapoff, int *bmapwords)
{
+ int nrpages = h >> HOBJ_PAGE_SHIFT, bitmapw;
+ size_t pagemapsz;
+
/*
* Return the size of the meta data required to map 'h' bytes
* of user memory in pages of HOBJ_PAGE_SIZE bytes. The meta
* data includes the length of the extent descriptor, plus the
-* length of the page mapping array. 'h' must be a multiple of
-* HOBJ_PAGE_SIZE on entry.
+* length of the page mapping array followed by the allocation
+* bitmap. 'h' must be a multiple of HOBJ_PAGE_SIZE on entry.
*/
assert((h & ~HOBJ_PAGE_MASK) == 0);
- return __align_to((h >> HOBJ_PAGE_SHIFT) * sizeof(struct page_entry)
- + sizeof(struct shared_extent), HOBJ_MINALIGNSZ);
+ pagemapsz = __align_to(nrpages * sizeof(struct page_entry),
+ sizeof(uint32_t));
+ bitmapw =__align_to(nrpages, 32) / 32;
+ if (bmapoff)
+ *bmapoff = offsetof(struct shared_extent, pagemap) + pagemapsz;
+ if (bmapwords)
+ *bmapwords = bitmapw;
+
+ return __align_to(pagemapsz
+ + sizeof(struct shared_extent)
+ + bitmapw * sizeof(uint32_t),
+ HOBJ_MINALIGNSZ);
}
static void init_extent(void *base, struct shared_extent *extent)
{
- caddr_t freepage;
int n, lastpgnum;
+ uint32_t *p;
__holder_init_nocheck(base, &extent->link);
@@ -147,19 +155,20 @@ static void init_extent(void *base, struct shared_extent
*extent)
assert(lastpgnum >= 1);
/* Mark each page as free in the page map. */
- for (n = 0, freepage = __shref(base, extent->membase);
-n < lastpgnum; n++, freepage += HOBJ_PAGE_SIZE) {
- *((memoff_t *)freepage) = __shoff(base, freepage) +
HOBJ_PAGE_SIZE;
+ for (n = 0; n <= lastpgnum; n++) {
extent->pagemap[n].type = page_free;
extent->pagemap[n].bcount = 0;
}
- *((memoff_t *)freepage) = 0;
- extent->pagemap[lastpgnum].type = page_free;
- extent->pagemap[lastpgnum].bcount = 0;
-
- /* The first page starts the free list of a new extent. */
- extent->freelist = extent->membase;
+ /* Clear the allocation bitmap. */
+ p = __shref(base, extent->bitmap);
+ memset(p, 0, extent->bitwords * sizeof(uint32_t));
+ /*
+* Mark the unused trailing bits (due to alignment) as busy,
+* we don't want to pick them since they don't map any actual
+* memory from the page pool.
+
[Xenomai-git] Philippe Gerum : copperplate/heapobj-pshared: introduce allocation bitmap
Module: xenomai-3
Branch: wip/heap-bitmap
Commit: 72ea1bdc6a12839c10326daf59564c2a16768e0c
URL:
http://git.xenomai.org/?p=xenomai-3.git;a=commit;h=72ea1bdc6a12839c10326daf59564c2a16768e0c
Author: Philippe Gerum
Date: Fri Jun 3 10:00:38 2016 +0200
copperplate/heapobj-pshared: introduce allocation bitmap
Using a free list leads to pathological execution times when releasing
blocks obtained from huge heaps (i.e. hundreds of megabytes). Rework
the core to use an allocation bitmap instead.
---
lib/copperplate/heapobj-pshared.c | 389 +
lib/copperplate/internal.h| 18 +-
2 files changed, 238 insertions(+), 169 deletions(-)
diff --git a/lib/copperplate/heapobj-pshared.c
b/lib/copperplate/heapobj-pshared.c
index 8c5dac6..2186d7c 100644
--- a/lib/copperplate/heapobj-pshared.c
+++ b/lib/copperplate/heapobj-pshared.c
@@ -28,6 +28,7 @@
#include
#include
#include
+#include
#include
#include
#include
@@ -43,15 +44,7 @@
#include "xenomai/init.h"
#include "internal.h"
-#define HOBJ_PAGE_SHIFT9 /* 2^9 => 512 bytes */
-#define HOBJ_PAGE_SIZE (1U << HOBJ_PAGE_SHIFT)
-#define HOBJ_PAGE_MASK (~(HOBJ_PAGE_SIZE-1))
-#define HOBJ_PAGE_ALIGN(addr) (((addr)+HOBJ_PAGE_SIZE-1)&HOBJ_PAGE_MASK)
-
-#define HOBJ_MINALIGNSZ (1U << 4) /* i.e. 16 bytes */
-#define HOBJ_MAXEXTSZ (1U << 31) /* i.e. 2Gb */
-
-enum {
+enum { /* FIXME: page_free redundant with future
bitmap */
page_free =0,
page_cont =1,
page_list =2
@@ -66,8 +59,9 @@ struct shared_extent {
struct holder link;
memoff_t membase; /* Base offset of page array */
memoff_t memlim;/* Offset limit of page array */
- memoff_t freelist; /* Head of free page list */
- struct page_entry pagemap[1]; /* Start of page map */
+ memoff_t bitmap;/* Offset of allocation bitmap */
+ int bitwords; /* 32bit words in bitmap */
+ struct page_entry pagemap[0]; /* Start of page map */
};
/*
@@ -117,24 +111,38 @@ static inline size_t __align_to(size_t size, size_t al)
return ((size+al-1)&(~(al-1)));
}
-static inline size_t get_pagemap_size(size_t h)
+static inline size_t get_pagemap_size(size_t h,
+ memoff_t *bmapoff, int *bmapwords)
{
+ int nrpages = h >> HOBJ_PAGE_SHIFT, bitmapw;
+ size_t pagemapsz;
+
/*
* Return the size of the meta data required to map 'h' bytes
* of user memory in pages of HOBJ_PAGE_SIZE bytes. The meta
* data includes the length of the extent descriptor, plus the
-* length of the page mapping array. 'h' must be a multiple of
-* HOBJ_PAGE_SIZE on entry.
+* length of the page mapping array followed by the allocation
+* bitmap. 'h' must be a multiple of HOBJ_PAGE_SIZE on entry.
*/
assert((h & ~HOBJ_PAGE_MASK) == 0);
- return __align_to((h >> HOBJ_PAGE_SHIFT) * sizeof(struct page_entry)
- + sizeof(struct shared_extent), HOBJ_MINALIGNSZ);
+ pagemapsz = __align_to(nrpages * sizeof(struct page_entry),
+ sizeof(uint32_t));
+ bitmapw =__align_to(nrpages, 32) / 32;
+ if (bmapoff)
+ *bmapoff = offsetof(struct shared_extent, pagemap) + pagemapsz;
+ if (bmapwords)
+ *bmapwords = bitmapw;
+
+ return __align_to(pagemapsz
+ + sizeof(struct shared_extent)
+ + bitmapw * sizeof(uint32_t),
+ HOBJ_MINALIGNSZ);
}
static void init_extent(void *base, struct shared_extent *extent)
{
- caddr_t freepage;
int n, lastpgnum;
+ uint32_t *p;
__holder_init_nocheck(base, &extent->link);
@@ -147,19 +155,20 @@ static void init_extent(void *base, struct shared_extent
*extent)
assert(lastpgnum >= 1);
/* Mark each page as free in the page map. */
- for (n = 0, freepage = __shref(base, extent->membase);
-n < lastpgnum; n++, freepage += HOBJ_PAGE_SIZE) {
- *((memoff_t *)freepage) = __shoff(base, freepage) +
HOBJ_PAGE_SIZE;
+ for (n = 0; n <= lastpgnum; n++) {
extent->pagemap[n].type = page_free;
extent->pagemap[n].bcount = 0;
}
- *((memoff_t *)freepage) = 0;
- extent->pagemap[lastpgnum].type = page_free;
- extent->pagemap[lastpgnum].bcount = 0;
-
- /* The first page starts the free list of a new extent. */
- extent->freelist = extent->membase;
+ /* Clear the allocation bitmap. */
+ p = __shref(base, extent->bitmap);
+ memset(p, 0, extent->bitwords * sizeof(uint32_t));
+ /*
+* Mark the unused trailing bits (due to alignment) as busy,
+* we don't want to pick them since they don't map any actual
+* memory from the page pool.
+
