Messages in this thread | | | Date | Sat, 5 Sep 1998 15:22:43 +0200 (MET DST) | From | Gerard Roudier <> | Subject | Re:Kernel programming Q: new aligned memory |
| |
On Fri, 4 Sep 1998, Inaky Perez Gonzalez wrote:
> >>>>> "B" == B James Phillippe <bryan@terran.org> writes: > > B> Hello Kernel Gurus, I'm wondering what is the best way to align a > B> chunk of kernel memory (from kmalloc, say) on a particular byte > B> boundary. 16 bytes, for instance. > > I had the same problem; however, I noticed everything was > using a power-of-two chunk allocation scheme, so I did a dirty > function [__usb_kmalloc_align]:
My minimal expectation from a kernel memory allocator is to provide at least alignment on the lowest power of 2 greater than the requested size. This can be achieved by using power of 2 sized actual memory chunks in the allocator. Such a scheme wastes 25% memory in average but provides lots of goodnesses and is simple to implement. Linux-2.0 kernel allocator does not provide such power of 2 alignments.
[ 5 minutes code removed ]
> The point is, if the size of the object is smaller then the > alignment, ask for a chunk sized as the alignment, else the size. The > rounding to the next power of two will do the same when > allocating.
If you want to align a object on a power of 2 greater than the lowest power of 2 greater than the object size, then you just want to waste memory, in my opinion. Do you really need that ?
> I've successfully allocated _everyone_ of them, even under > heavy load, but I am not sure it will always success. So I implemented > a workaround for the case it failed. > > If not aligned, it will recursively allocate more chunks, > until one falls into the wanted alignment; then it will free them and > let you with the aligned one. It's ugly, but it works. There's a depth > limit, just in case ... > > It's dirty, could be optimized, etc, etc ... but hey, I did it > in five minutes :)
Most of things we did in five minutes or less generally donnot smell good. :-))
BTW, I have attached the allocator code I use in latest experimental sym53c8xx driver for linux-2.0, if this can help. Seems Linux-2.1 provides the expected power of 2 alignment, but drivers have to work for linux-2.0 too.
Regards, Gerard. /* ** Simple power of two buddy-like allocator ** ---------------------------------------- ** This simple code is not intended to be fast, but to provide ** power of 2 aligned memory allocations. ** Since the SCRIPTS processor only supplies 8 bit arithmetic, ** this allocator allows simple and fast address calculations ** from the SCRIPTS code. In addition, cache line alignment ** is guaranteed for power of 2 cache line size. */
#define MEMO_SHIFT 4 /* 16 bytes minimum memory chunk */ #define MEMO_PAGE_ORDER 0 /* 1 PAGE maximum (for now (ever?) */ typedef unsigned long addr; /* Enough bits to bit-hack addresses */
#define MEMO_FREE_UNUSED /* Free unused pages immediately */
struct m_link { struct m_link *next; /* Simple links are enough */ };
#ifndef GFP_DMA_32BIT #define GFP_DMA_32BIT 0 /* Will this flag ever exist */ #endif
#if LINUX_VERSION_CODE >= LinuxVersionCode(2,1,0) #define get_pages(order) __get_free_pages(GFP_ATOMIC | GFP_DMA_32BIT, order) #else #define get_pages(order) __get_free_pages(GFP_ATOMIC | GFP_DMA_32BIT, order, 0) #endif
/* ** Lists of available memory chunks. ** Starts with 16 bytes chunks until 1 PAGE chunks. */ static struct m_link h[PAGE_SHIFT-MEMO_SHIFT+MEMO_PAGE_ORDER+1];
/* ** Allocate a memory area aligned on the lowest power of 2 ** greater than the requested size. */ static void *__m_alloc(int size) { int i = 0; int s = (1 << MEMO_SHIFT); int j; addr a ;
if (size > (PAGE_SIZE << MEMO_PAGE_ORDER)) return 0;
while (size > s) { s <<= 1; ++i; }
j = i; while (!h[j].next) { if (s == (PAGE_SIZE << MEMO_PAGE_ORDER)) { h[j].next = (struct m_link *)get_pages(MEMO_PAGE_ORDER); if (h[j].next) h[j].next->next = 0; break; } ++j; s <<= 1; } a = (addr) h[j].next; if (a) { h[j].next = h[j].next->next; while (j > i) { j -= 1; s >>= 1; h[j].next = (struct m_link *) (a+s); h[j].next->next = 0; } } #ifdef DEBUG printk("m_alloc(%d) = %p\n", size, (void *) a); #endif return (void *) a; }
/* ** Free a memory area allocated using m_alloc(). ** Coalesce buddies. ** Free pages that become unused if MEMO_FREE_UNUSED is defined. */ static void __m_free(void *ptr, int size) { int i = 0; int s = (1 << MEMO_SHIFT); struct m_link *q; addr a, b;
#ifdef DEBUG printk("m_free(%p, %d)\n", ptr, size); #endif
if (size > (PAGE_SIZE << MEMO_PAGE_ORDER)) return;
while (size > s) { s <<= 1; ++i; }
a = (addr) ptr;
while (1) { #ifdef MEMO_FREE_UNUSED if (s == (PAGE_SIZE << MEMO_PAGE_ORDER)) { free_pages(a, MEMO_PAGE_ORDER); break; } #endif b = a ^ s; q = &h[i]; while (q->next && q->next != (struct m_link *) b) { q = q->next; } if (!q->next) { ((struct m_link *) a)->next = h[i].next; h[i].next = (struct m_link *) a; break; } q->next = q->next->next; a = a & b; s <<= 1; ++i; } }
| |