/*      $NetBSD: aml_memman.c,v 1.3 2009/01/18 09:46:59 lukem Exp $     */

/*-
* Copyright (c) 1999, 2000 Mitsuru IWASAKI <[email protected]>
* All rights reserved.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions
* are met:
* 1. Redistributions of source code must retain the above copyright
*    notice, this list of conditions and the following disclaimer.
* 2. Redistributions in binary form must reproduce the above copyright
*    notice, this list of conditions and the following disclaimer in the
*    documentation and/or other materials provided with the distribution.
*
* THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
* ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
* IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
* ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
* FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
* DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
* OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
* HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
* LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
* OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
* SUCH DAMAGE.
*
*      Id: aml_memman.c,v 1.10 2000/08/09 14:47:43 iwasaki Exp
*      $FreeBSD: src/usr.sbin/acpi/amldb/aml/aml_memman.c,v 1.2 2000/11/09 06:24:45 iwasaki Exp $
*/
#include <sys/cdefs.h>
__RCSID("$NetBSD: aml_memman.c,v 1.3 2009/01/18 09:46:59 lukem Exp $");

/*
* Generic Memory Management
*/

#include <sys/param.h>

#include <aml/aml_memman.h>

#ifndef _KERNEL
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#else /* _KERNEL */
#include <sys/kernel.h>
#include <sys/systm.h>
#include <sys/malloc.h>
MALLOC_DEFINE(M_MEMMAN, "memman", "Generic and Simple Memory Management");
#endif /* !_KERNEL */

unsigned int    memid_unkown = 255;

static int               manage_block(struct memman *memman, unsigned int id,
                                     void *block, unsigned static_mem,
                                     unsigned entries);
static int               blockman_init(struct memman *memman, unsigned int id);
static void              memman_flexsize_add_histogram(struct memman *memman,
                                                      size_t size,
                                                      int tolerance);
static int               memman_comp_histogram_size(const void *a,
                                                   const void *b);
static void              memman_sort_histogram_by_size(struct memman *memman);
static unsigned int      memman_guess_memid(struct memman *memman, void *chunk);
static void              memman_statistics_fixedsize(struct memman *memman);
static void              memman_statistics_flexsize(struct memman *memman);

static int
manage_block(struct memman *memman, unsigned int id, void *block,
   unsigned static_mem, unsigned entries)
{
       unsigned int    i;
       size_t  alloc_size;
       void    *tmp, *realblock;
       struct  memman_blockman *bmp;
       struct  memman_block *memblock;
       struct  memman_node *memnodes;

       bmp = &memman->blockman[id];
       alloc_size = MEMMAN_BLOCKNODE_SIZE(entries);

       if (static_mem) {
               tmp = (void *)block;
               realblock = (char *)block + alloc_size;
       } else {
               tmp = MEMMAN_SYSMALLOC(alloc_size);
               if (!tmp) {
                       return (-1);
               }
               realblock = block;

               memman->allocated_mem += alloc_size;
               memman->salloc_called++;
       }

       memblock = (struct memman_block *)tmp;
       memnodes = (struct memman_node *)((char *)tmp + sizeof(struct memman_block));

       memblock->block = realblock;
       memblock->static_mem = static_mem;
       memblock->allocated = entries;
       memblock->available = entries;
       if (!static_mem) {
               alloc_size += roundup(bmp->size * entries, ROUNDUP_UNIT);
       }
       memblock->allocated_mem = alloc_size;
       LIST_INSERT_HEAD(&bmp->block_list, memblock, links);

       for (i = 0; i < entries; ++i) {
               memnodes[i].node = ((char *)realblock + (i * (bmp->size)));
               memnodes[i].memblock = memblock;
               LIST_INSERT_HEAD(&bmp->free_node_list, &memnodes[i], links);
       }
       bmp->available = entries;

       return (0);
}

static int
blockman_init(struct memman *memman, unsigned int id)
{
       int     status;
       struct  memman_blockman *bmp;

       bmp = &memman->blockman[id];
       bmp->initialized = 1;
       LIST_INIT(&bmp->block_list);
       LIST_INIT(&bmp->free_node_list);
       LIST_INIT(&bmp->occupied_node_list);
       status = manage_block(memman, id, bmp->initial_block,
           1, MEMMAN_INITIAL_SIZE);
       return (status);
}

void *
memman_alloc(struct memman *memman, unsigned int id)
{
       size_t  alloc_size;
       void    *chunk, *block;
       struct  memman_blockman *bmp;
       struct  memman_node *memnode;

       if (memman->max_memid <= id) {
               printf("memman_alloc: invalid memory type id\n");
               return (NULL);
       }
       bmp = &memman->blockman[id];
       if (!bmp->initialized) {
               if (blockman_init(memman, id)) {
                       goto malloc_fail;
               }
       }
       memman->alloc_called++;

       if (bmp->available == 0) {
               alloc_size = roundup(bmp->size * MEMMAN_INCR_SIZE,
                   ROUNDUP_UNIT);
               block = MEMMAN_SYSMALLOC(alloc_size);
               if (!block) {
                       goto malloc_fail;
               }
               memman->required_mem += bmp->size * MEMMAN_INCR_SIZE;
               memman->allocated_mem += alloc_size;
               memman->salloc_called++;

               if (manage_block(memman, id, block, 0, MEMMAN_INCR_SIZE)) {
                       goto malloc_fail;
               }
       }
       memnode = LIST_FIRST(&bmp->free_node_list);
       LIST_REMOVE(memnode, links);
       chunk = memnode->node;
       LIST_INSERT_HEAD(&bmp->occupied_node_list, memnode, links);
       memnode->memblock->available--;
       bmp->available--;

       return (chunk);

malloc_fail:
       printf("memman_alloc: could not allocate memory\n");
       return (NULL);
}

static void
memman_flexsize_add_histogram(struct memman *memman, size_t size,
   int tolerance)
{
       unsigned int i;
       int     gap;

       if (size == 0) {
               return;
       }
       for (i = 0; i < memman->flex_mem_histogram_ptr; i++) {
               gap = memman->flex_mem_histogram[i].mem_size - size;
               if (gap >= (tolerance * -1) && gap <= tolerance) {
                       memman->flex_mem_histogram[i].count++;
                       if (memman->flex_mem_histogram[i].mem_size < size) {
                               memman->flex_mem_histogram[i].mem_size = size;
                       }
                       return;
               }
       }

       if (memman->flex_mem_histogram_ptr == MEMMAN_HISTOGRAM_SIZE) {
               memman_flexsize_add_histogram(memman, size, tolerance + 1);
               return;
       }
       i = memman->flex_mem_histogram_ptr;
       memman->flex_mem_histogram[i].mem_size = size;
       memman->flex_mem_histogram[i].count = 1;
       memman->flex_mem_histogram_ptr++;
}

static int
memman_comp_histogram_size(const void *a, const void *b)
{
       int     delta;

       delta = ((const struct memman_histogram *)a)->mem_size -
           ((const struct memman_histogram *)b)->mem_size;
       return (delta);
}

static void
memman_sort_histogram_by_size(struct memman *memman)
{
       qsort(memman->flex_mem_histogram, memman->flex_mem_histogram_ptr,
           sizeof(struct memman_histogram), memman_comp_histogram_size);
}

void *
memman_alloc_flexsize(struct memman *memman, size_t size)
{
       void    *mem;
       struct  memman_flexmem_info *info;

       if (size == 0) {
               return (NULL);
       }
       if ((mem = MEMMAN_SYSMALLOC(size)) != NULL) {   /* XXX */

               info = MEMMAN_SYSMALLOC(sizeof(struct memman_flexmem_info));
               if (info) {
                       if (!memman->flex_mem_initialized) {
                               LIST_INIT(&memman->flexmem_info_list);
                               bzero(memman->flex_mem_histogram,
                                   sizeof(struct memman_histogram));
                               memman->flex_mem_initialized = 1;
                       }
                       info->addr = mem;
                       info->mem_size = size;
                       LIST_INSERT_HEAD(&memman->flexmem_info_list, info, links);
               }
               memman->flex_alloc_called++;
               memman->flex_salloc_called++;
               memman->flex_required_mem += size;
               memman->flex_allocated_mem += size;
               if (memman->flex_mem_size_min == 0 ||
                   memman->flex_mem_size_min > size) {
                       memman->flex_mem_size_min = size;
               }
               if (memman->flex_mem_size_max < size) {
                       memman->flex_mem_size_max = size;
               }
               if (memman->flex_peak_mem_usage <
                   (memman->flex_allocated_mem - memman->flex_reclaimed_mem)) {
                       memman->flex_peak_mem_usage =
                           (memman->flex_allocated_mem - memman->flex_reclaimed_mem);
               }
               memman_flexsize_add_histogram(memman, size,
                   memman->flex_mem_histogram_initial_tolerance);
       }
       return (mem);
}

static unsigned int
memman_guess_memid(struct memman *memman, void *chunk)
{
       unsigned int    id;
       struct  memman_blockman *bmp;
       struct  memman_node *memnode;

       for (id = 0; id < memman->max_memid; id++) {
               bmp = &memman->blockman[id];
               if (!bmp->initialized) {
                       if (blockman_init(memman, id)) {
                               printf("memman_free: could not initialized\n");
                       }
               }
               LIST_FOREACH(memnode, &bmp->occupied_node_list, links) {
                       if (memnode->node == chunk) {
                               return (id);    /* got it! */
                       }
               }
       }
       return (memid_unkown);  /* gave up */
}

void
memman_free(struct memman *memman, unsigned int memid, void *chunk)
{
       unsigned int    id;
       unsigned        found;
       void    *block;
       struct  memman_blockman *bmp;
       struct  memman_block *memblock;
       struct  memman_node *memnode;

       id = memid;
       if (memid == memid_unkown) {
               id = memman_guess_memid(memman, chunk);
       }
       if (memman->max_memid <= id) {
               printf("memman_free: invalid memory type id\n");
               MEMMAN_SYSABORT();
               return;
       }
       bmp = &memman->blockman[id];
       if (!bmp->initialized) {
               if (blockman_init(memman, id)) {
                       printf("memman_free: could not initialized\n");
               }
       }
       found = 0;
       LIST_FOREACH(memnode, &bmp->occupied_node_list, links) {
               if (memnode->node == chunk) {
                       found = 1;
                       break;
               }
       }
       if (!found) {
               printf("memman_free: invalid address\n");
               return;
       }
       memman->free_called++;

       LIST_REMOVE(memnode, links);
       memblock = memnode->memblock;
       memblock->available++;
       LIST_INSERT_HEAD(&bmp->free_node_list, memnode, links);
       bmp->available++;

       if (!memblock->static_mem &&
           memblock->available == memblock->allocated) {
               LIST_FOREACH(memnode, &bmp->free_node_list, links) {
                       if (memnode->memblock != memblock) {
                               continue;
                       }
                       LIST_REMOVE(memnode, links);
                       bmp->available--;
               }
               block = memblock->block;
               MEMMAN_SYSFREE(block);
               memman->sfree_called++;

               LIST_REMOVE(memblock, links);
               memman->sfree_called++;
               memman->reclaimed_mem += memblock->allocated_mem;
               MEMMAN_SYSFREE(memblock);
       }
}

void
memman_free_flexsize(struct memman *memman, void *chunk)
{
       struct  memman_flexmem_info *info;

       LIST_FOREACH(info, &memman->flexmem_info_list, links) {
               if (info->addr == chunk) {
                       memman->flex_reclaimed_mem += info->mem_size;
                       LIST_REMOVE(info, links);
                       MEMMAN_SYSFREE(info);
                       break;
               }
       }
       /* XXX */
       memman->flex_free_called++;
       memman->flex_sfree_called++;
       MEMMAN_SYSFREE(chunk);
}

void
memman_freeall(struct memman *memman)
{
       unsigned int id;
       void    *chunk;
       struct  memman_blockman *bmp;
       struct  memman_node *memnode;
       struct  memman_block *memblock;
       struct  memman_flexmem_info *info;

       for (id = 0; id < memman->max_memid; id++) {
               bmp = &memman->blockman[id];

               while ((memnode = LIST_FIRST(&bmp->occupied_node_list))) {
                       chunk = memnode->node;
                       printf("memman_freeall: fixed size (id = %u)\n", id);
                       memman_free(memman, id, chunk);
               }
               while ((memblock = LIST_FIRST(&bmp->block_list))) {
                       LIST_REMOVE(memblock, links);
                       if (!memblock->static_mem) {
                               memman->sfree_called++;
                               memman->reclaimed_mem += memblock->allocated_mem;
                               MEMMAN_SYSFREE(memblock);
                       }
               }
               bmp->initialized = 0;
       }

       LIST_FOREACH(info, &memman->flexmem_info_list, links) {
               printf("memman_freeall: flex size (size = %zd, addr = %p)\n",
                   info->mem_size, info->addr);
               memman_free_flexsize(memman, info->addr);
       }
}

static void
memman_statistics_fixedsize(struct memman *memman)
{
       printf("  fixed size memory blocks\n");
       printf("    alloc():            %d times\n", memman->alloc_called);
       printf("    system malloc():    %d times\n", memman->salloc_called);
       printf("    free():             %d times\n", memman->free_called);
       printf("    system free():      %d times\n", memman->sfree_called);
       printf("    required memory:    %zd bytes\n", memman->required_mem);
       printf("    allocated memory:   %zd bytes\n", memman->allocated_mem);
       printf("    reclaimed memory:   %zd bytes\n", memman->reclaimed_mem);
}

static void
memman_statistics_flexsize(struct memman *memman)
{
       unsigned int    i;

       printf("  flexible size memory blocks\n");
       printf("    alloc():            %d times\n", memman->flex_alloc_called);
       printf("    system malloc():    %d times\n", memman->flex_salloc_called);
       printf("    free():             %d times\n", memman->flex_free_called);
       printf("    system free():      %d times\n", memman->flex_sfree_called);
       printf("    required memory:    %zd bytes\n", memman->flex_required_mem);
       printf("    allocated memory:   %zd bytes\n", memman->flex_allocated_mem);
       printf("    reclaimed memory:   %zd bytes\n", memman->flex_reclaimed_mem);
       printf("    peak memory usage:  %zd bytes\n", memman->flex_peak_mem_usage);
       printf("    min memory size:    %zd bytes\n", memman->flex_mem_size_min);
       printf("    max memory size:    %zd bytes\n", memman->flex_mem_size_max);
       printf("    avg memory size:    %zd bytes\n",
           (memman->flex_alloc_called) ?
           memman->flex_allocated_mem / memman->flex_alloc_called : 0);

       printf("    memory size histogram (%d entries):\n",
           memman->flex_mem_histogram_ptr);
       printf("        size    count\n");
       memman_sort_histogram_by_size(memman);
       for (i = 0; i < memman->flex_mem_histogram_ptr; i++) {
               printf("        %zu     %d\n",
                   memman->flex_mem_histogram[i].mem_size,
                   memman->flex_mem_histogram[i].count);
       }
}

void
memman_statistics(struct memman *memman)
{
       printf("memman: reporting statistics\n");
       memman_statistics_fixedsize(memman);
       memman_statistics_flexsize(memman);
}

size_t
memman_memid2size(struct memman *memman, unsigned int id)
{
       if (memman->max_memid <= id) {
               printf("memman_alloc: invalid memory type id\n");
               return (0);
       }
       return (memman->blockman[id].size);
}

You are viewing proxied material from ftp.icm.edu.pl. The copyright of proxied material belongs to its original authors. Any comments or complaints in relation to proxied material should be directed to the original authors of the content concerned. Please see the disclaimer for more details.