lkml.org 
[lkml]   [1998]   [Sep]   [5]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
/
Date
From
SubjectRe: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;
}
}
\
 
 \ /
  Last update: 2005-03-22 13:44    [W:0.042 / U:2.760 seconds]
©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site