[Berlin-wireless] [OT] Brauch nen Job! ;/ (n/t)
Alina Friedrichsen
x-alina
Mo Dez 8 20:26:03 CET 2008
> Mit Allocations-Algorithmen hab ich mich bis jetzt nur im
> "eindimensionalen Bereich" beschaeftigt in Form einer malloc()-Funktion fuer den
> Kernel-Space beschaeftigt. Ich eigne mir immer das Wissen an, was ich grade brauche.
Hab ich vor rund 8 Jahren geschrieben.
Schoen flotter malloc()-Algorithmus:
struct block_header
{
struct block_header *next;
};
struct page_header
{
struct page_header *next;
struct page_header *previous;
struct block_header *first_free_block;
unsigned short nsize;
unsigned short full;
};
struct size_struct
{
unsigned int size;
struct page_header *first_free_page;
};
struct page_header *new_kmalloc_page(unsigned short nsize);
void *kmalloc(size_t size);
void kfree(void *ptr);
static spinlock_t kmalloc_lock;
static struct size_struct sizes[] = {
{16, NULL},
{32, NULL},
{64, NULL},
{127, NULL},
{255, NULL},
{510, NULL},
{1020, NULL},
{2040, NULL},
};
struct page_header *new_kmalloc_page(unsigned short nsize)
{
struct page_header *page_header;
struct block_header *block_header;
unsigned short size;
page_header = PAGE2PTR(get_free_page(GFP_KERNEL));
if(page_header == NULL) return NULL;
size = sizes[nsize].size;
page_header->next = NULL;
page_header->previous = NULL;
page_header->first_free_block = ((void *) page_header) + sizeof(struct page_header);
page_header->nsize = nsize;
page_header->full = 0;
block_header = page_header->first_free_block;
block_header->next = (void *) block_header + size;
while(((void *) block_header->next + size) <= ((void *) page_header + PAGE_SIZE))
{
block_header = block_header->next;
block_header->next = (void *) block_header + size;
}
block_header->next = NULL;
return page_header;
}
void *kmalloc(size_t size)
{
struct block_header *bh;
int i;
// Die richtige Grösse suchen...
if(size > 2040)
{
if(size > PAGE_SIZE) return vmalloc(size);
else return PAGE2PTR(get_free_page(GFP_KERNEL));
}
for(i = 0; size > sizes[i].size; i++);
// Wenn keine freie Page in der liste ist, wird
// eine neue allociert...
spin_lock(&kmalloc_lock);
if(sizes[i].first_free_page == NULL)
{
sizes[i].first_free_page = new_kmalloc_page(i);
if(sizes[i].first_free_page == NULL)
{
spin_unlock(&kmalloc_lock);
return NULL;
}
}
// Freien Block aus der Liste nehmen...
bh = (void *) sizes[i].first_free_page->first_free_block;
sizes[i].first_free_page->first_free_block = bh->next;
sizes[i].first_free_page->full++;
// Wenn die Page jetzt keine freien Blöcke mehr hat,
// wird sie aus der Liste entfernt...
if(sizes[i].first_free_page->first_free_block == NULL)
{
sizes[i].first_free_page = sizes[i].first_free_page->next;
if(sizes[i].first_free_page != NULL)
{
sizes[i].first_free_page->previous = NULL;
}
}
// Bye, bye...
spin_unlock(&kmalloc_lock);
return (void *) bh;
}
void kfree(void *ptr)
{
unsigned int pn;
struct page_header *ph;
struct block_header *bh; // :)
unsigned short ns;
struct page_header *pi;
// NULL-Pointer?
if(ptr == NULL) return;
// Ganze Page?
if(IS_PAGE((uintptr_t) ptr))
{
if((uintptr_t) ptr >= VMEM_OFFSET) vfree(ptr);
else free_page(PTR2PAGE(ptr));
return;
}
// Infos ermitteln...
spin_lock(&kmalloc_lock);
bh = (struct block_header *) ptr;
pn = PTR2PAGE(ptr);
ph = PAGE2PTR(pn);
ns = ph->nsize;
// Block wieder freigeben...
bh->next = ph->first_free_block;
ph->first_free_block = bh;
ph->full--;
// Wenn die Page jetzt frei und nicht die
// letzte ist, wird sie freigegeben...
if(ph->full < 1 && (ph->next != NULL || ph->previous != NULL))
{
// Page aus der Liste austragen...
if(ph->previous == NULL)
{
// Wenn die Page die letzte ist
sizes[ns].first_free_page = ph->next;
if(sizes[ns].first_free_page != NULL)
{
sizes[ns].first_free_page->previous = NULL;
}
}
else
{
ph->previous->next = ph->next;
if(ph->next != NULL)
{
ph->next->previous = ph->previous;
}
}
// Page freigeben...
free_page(pn);
}
// Wenn die Page, weil sie voll war, aus der Liste geworfen
// wurde, wird sie jetzt wieder eingefügt...
else if(bh->next == NULL)
{
ph->next = sizes[ns].first_free_page;
ph->previous = NULL;
sizes[ns].first_free_page = ph;
if(ph->next != NULL)
{
ph->next->previous = ph;
}
}
spin_unlock(&kmalloc_lock);
return;
}
--
Sensationsangebot verlängert: GMX FreeDSL - Telefonanschluss + DSL
für nur 16,37 Euro/mtl.!* http://dsl.gmx.de/?ac=OM.AD.PD003K1308T4569a
Mehr Informationen über die Mailingliste Berlin