lkml.org 
[lkml]   [1998]   [Sep]   [5]   [last100]   RSS Feed
Views: [more markup]  [less markup]  [headers]  [forward] 
 
Messages in this thread
/
DateSat, 5 Sep 1998 15:22:43 +0200 (MET DST)
FromGerard Roudier <>
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    [from the cache]
©2003-2008