LCOV - code coverage report
Current view: top level - src - memory.c (source / functions) Hit Total Coverage
Test: libtrbase 1.0.2 Lines: 44 72 61.1 %
Date: 2016-03-25 15:13:20 Functions: 6 9 66.7 %
Legend: Lines: hit not hit | Branches: + taken - not taken # not executed Branches: 0 0 -

           Branch data     Line data    Source code
       1                 :            : /**
       2                 :            :  * \file This holds all stufff related our memory managent.
       3                 :            :  * I try the best as far as I can to reduce memory fragmentation
       4                 :            :  * and unneccessary calls to alloc and free.
       5                 :            :  *
       6                 :            :  * To achive this I try an approach described here as "Quick Fit".
       7                 :            :  * http://www.flounder.com/memory_allocation.htm
       8                 :            :  *
       9                 :            :  * The basic idea is to keep allocated memory segments and don't free
      10                 :            :  * them again. Instead I will put them in a tree indexed by their size.
      11                 :            :  * To get new memory I first have a look in the tree if there is
      12                 :            :  * a fitting memory segment. Fitting mean, larger or exactly the size
      13                 :            :  * I need. If there is one, use it. If not create a new one using 
      14                 :            :  * usual malloc approach.
      15                 :            :  * I won't split the reagions at all because most likely they will be
      16                 :            :  * free soon again. This way I might waste some memory, so I have to
      17                 :            :  * keep an eye on this.
      18                 :            :  *
      19                 :            :  * Right now I don't build an upper limit for allocation. The limit
      20                 :            :  * still is the system memory itself.
      21                 :            :  *
      22                 :            :  * This is not implemented as a class because it will be used in the 
      23                 :            :  * process of object creation.
      24                 :            :  *
      25                 :            :  * The data structure is a balanced tree with size as key.
      26                 :            :  * Under the size key is a list of elements of the same size.
      27                 :            :  *
      28                 :            :  * \author      Georg Hopp
      29                 :            :  *
      30                 :            :  * \copyright
      31                 :            :  * Copyright © 2014 Georg Hopp
      32                 :            :  *
      33                 :            :  * This program is free software: you can redistribute it and/or modify
      34                 :            :  * it under the terms of the GNU General Public License as published by
      35                 :            :  * the Free Software Foundation, either version 3 of the License, or
      36                 :            :  * (at your option) any later version.
      37                 :            :  *
      38                 :            :  * This program is distributed in the hope that it will be useful,
      39                 :            :  * but WITHOUT ANY WARRANTY; without even the implied warranty of
      40                 :            :  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
      41                 :            :  * GNU General Public License for more details.
      42                 :            :  *
      43                 :            :  * You should have received a copy of the GNU General Public License
      44                 :            :  * along with this program.  If not, see <http://www.gnu.org/licenses/>.
      45                 :            :  */
      46                 :            : 
      47                 :            : #define _GNU_SOURCE
      48                 :            : 
      49                 :            : #include <stdio.h>
      50                 :            : 
      51                 :            : #include <stdlib.h>
      52                 :            : #include <string.h>
      53                 :            : #include <search.h>
      54                 :            : #include <unistd.h>
      55                 :            : #include <stdint.h>
      56                 :            : 
      57                 :            : #include "tr/memory.h"
      58                 :            : 
      59                 :            : #ifdef _WIN32
      60                 :            : #define _SC_PAGESIZE 2048L
      61                 :            : 
      62                 :            : long
      63                 :            : sysconf(int name)
      64                 :            : {
      65                 :            :         switch (name) {
      66                 :            :                 case _SC_PAGESIZE: return 2048L;
      67                 :            :         }
      68                 :            : 
      69                 :            :         return -1;
      70                 :            : }
      71                 :            : #endif
      72                 :            : 
      73                 :            : extern inline int    TR_bitwidth(size_t);
      74                 :            : extern inline size_t TR_getSize(void *);
      75                 :            : extern inline size_t TR_getUsableSize(void *);
      76                 :            : extern inline int    TR_getIdx(void *);
      77                 :            : 
      78                 :            : static
      79                 :            : struct memSegment *
      80                 :          2 : newElement(size_t size, int idx)
      81                 :            : {
      82                 :          2 :     struct memSegment * element = malloc(size);
      83                 :            : 
      84                 :          2 :         element->ref_count = 1;
      85                 :          2 :     element->size      = size;
      86                 :          2 :     element->idx       = idx;
      87                 :          2 :     element->ptr       = (void*)element + sizeof(struct memSegment);
      88                 :            : 
      89                 :          2 :     element->next      = NULL;
      90                 :            : 
      91                 :          2 :     return element;
      92                 :            : }
      93                 :            : 
      94                 :            : #ifdef MEM_OPT
      95                 :            : /**
      96                 :            :  * insert element in tree
      97                 :            :  */
      98                 :            : static
      99                 :            : inline
     100                 :            : struct memSegment *
     101                 :          5 : insertElement(struct memSegment ** stack, struct memSegment * element)
     102                 :            : {
     103                 :          5 :         element->next = *stack;
     104                 :          5 :         *stack        = element;
     105                 :            : 
     106                 :          5 :         return element;
     107                 :            : }
     108                 :            : 
     109                 :            : static
     110                 :            : inline
     111                 :            : struct memSegment *
     112                 :          5 : deleteElement(struct memSegment ** stack)
     113                 :            : {
     114                 :          5 :         struct memSegment * del_node = *stack;
     115                 :            : 
     116                 :          5 :         if (*stack) {
     117                 :          3 :                 *stack = (*stack)->next;
     118                 :            :         }
     119                 :            : 
     120                 :          5 :         return del_node;
     121                 :            : }
     122                 :            : 
     123                 :            : #define TR_MAX_MEM_IDX  1024
     124                 :            : 
     125                 :            : struct memSegment * segments[TR_MAX_MEM_IDX] = {};
     126                 :            : 
     127                 :            : static
     128                 :            : inline
     129                 :            : void
     130                 :            : segmentFree(struct memSegment * segment, int depth)
     131                 :            : {
     132                 :            :     while (NULL != segment) {
     133                 :            :         struct memSegment * next = segment->next;
     134                 :            :         free(segment);
     135                 :            :         segment = next;
     136                 :            :     }
     137                 :            : }
     138                 :            : #endif
     139                 :            : 
     140                 :            : void *
     141                 :          0 : TR_reference(void * mem)
     142                 :            : {
     143                 :          0 :         struct memSegment * seg = (mem - sizeof(struct memSegment));
     144                 :            : 
     145                 :          0 :         seg->ref_count++;
     146                 :            : 
     147                 :          0 :         return mem;
     148                 :            : }
     149                 :            : 
     150                 :            : /*
     151                 :            :  * This tries to reflect the memory management behaviour of the
     152                 :            :  * GNU version of malloc. For other versions this might need
     153                 :            :  * to be changed to be optimal.
     154                 :            :  *
     155                 :            :  * However, GNU malloc keeps separate pools for each power of
     156                 :            :  * 2 memory size up to page size. So one page consists all of
     157                 :            :  * memory blocks of the same sizei (a power of 2).
     158                 :            :  *
     159                 :            :  * Also as far as I understand the smallest allocatable block is
     160                 :            :  * 8 bytes. At least the adresses are alwayse a multiple of 8.
     161                 :            :  *
     162                 :            :  * So lets say page size is 4096. There is nothing allocated
     163                 :            :  * right now. We allocate a block of 8 bytes. This will request
     164                 :            :  * a memory page from the OS. Then define it as a page containing
     165                 :            :  * 8 byte blocks and return the address of the first one of these.
     166                 :            :  * Any subsequent call to malloc for 8 bytes will return one of the
     167                 :            :  * blocks within this page as long as there are some left.
     168                 :            :  *
     169                 :            :  * So what we do here is up to page size round the request size up
     170                 :            :  * to the next power of 2 >= 8.
     171                 :            :  * Sizes greater then pagesize will be round up to the next
     172                 :            :  * multiple of pagesize. As far as I understand these are not
     173                 :            :  * pooled anyway.
     174                 :            :  *
     175                 :            :  * For now this assumes we are on a little endian machine.
     176                 :            :  */
     177                 :            : void *
     178                 :          5 : TR_malloc(size_t size)
     179                 :            : {
     180                 :          5 :         struct memSegment * seg         = NULL;
     181                 :          5 :         long                psize       = sysconf(_SC_PAGESIZE);
     182                 :            :         static int          psize_width = 0;
     183                 :            :         int                 idx;
     184                 :            : 
     185                 :          5 :         psize_width = psize_width ? psize_width : TR_bitwidth(psize);
     186                 :            : 
     187                 :          5 :         size += sizeof(struct memSegment);
     188                 :            : 
     189                 :            : #define MIN_BITS   8
     190                 :            : 
     191                 :          5 :     if (size >= psize) {
     192                 :            :                 // get a multiple of pagesize
     193                 :          0 :         idx = size / psize;
     194                 :            : 
     195                 :          0 :         if (0 != (size % psize)) {
     196                 :            :             // size if not a multiple of pagesize so bring it to one.
     197                 :          0 :             idx++;
     198                 :          0 :             size = idx * psize;
     199                 :            :         }
     200                 :            : 
     201                 :          0 :         idx += psize_width - MIN_BITS;
     202                 :            :     } else {
     203                 :          5 :         if (size <= 1 << (MIN_BITS - 1)) {
     204                 :          5 :             size = 1 << (MIN_BITS - 1);
     205                 :          5 :             idx = 0;
     206                 :            :         } else {
     207                 :            :                         // size-1 to ensure that powers of two will not be
     208                 :            :                         // changed to the next power of two
     209                 :          0 :             idx   = TR_bitwidth(size-1) + 1;
     210                 :          0 :                         size  = 1 << idx;
     211                 :          0 :             idx  -= (MIN_BITS - 1);
     212                 :            :         }
     213                 :            :     }
     214                 :            : 
     215                 :            : #undef MIN_BITS
     216                 :            : 
     217                 :            : #ifdef MEM_OPT
     218                 :          5 :         if (idx < TR_MAX_MEM_IDX) {
     219                 :          5 :                 seg = deleteElement(&(segments[idx]));
     220                 :            :         } else
     221                 :            : #endif
     222                 :            :         {
     223                 :          0 :                 idx = -1;
     224                 :            :         }
     225                 :            : 
     226                 :          5 :         if (NULL == seg) {
     227                 :          2 :                 seg = newElement(size, idx);
     228                 :            :         }
     229                 :            : 
     230                 :          5 :         return seg->ptr;
     231                 :            : }
     232                 :            : 
     233                 :            : /**
     234                 :            :  * this is a really memory wasting solution....just to be able to
     235                 :            :  * use calloc, which might be faster then malloc/memset solution.
     236                 :            :  *
     237                 :            :  * Maybe this is a bad idea, as we need to memset the buffer anyway
     238                 :            :  * if it comes from our tree, which hopefully should be the majority
     239                 :            :  * of cases.
     240                 :            :  */
     241                 :            : void *
     242                 :          5 : TR_calloc(size_t nmemb, size_t size)
     243                 :            : {
     244                 :          5 :         size_t   _size = nmemb * size;
     245                 :          5 :         void   * mem   = TR_malloc(_size);
     246                 :            : 
     247                 :          5 :         memset(mem, 0, TR_getUsableSize(mem));
     248                 :            : 
     249                 :          5 :         return mem;
     250                 :            : }
     251                 :            : 
     252                 :            : void
     253                 :          5 : TR_free(void ** mem)
     254                 :            : {
     255                 :          5 :         if (NULL != *mem) {
     256                 :          5 :                 struct memSegment * seg = (*mem - sizeof(struct memSegment));
     257                 :            : 
     258                 :          5 :                 if (1 < seg->ref_count) {
     259                 :          0 :                         seg->ref_count--;
     260                 :            :                 } else {
     261                 :            : #ifdef MEM_OPT
     262                 :          5 :                         if (-1 != seg->idx) {
     263                 :          5 :                                 insertElement(&(segments[seg->idx]), seg);
     264                 :            :                         } else
     265                 :            : #endif
     266                 :            :                         {
     267                 :          0 :                                 free(seg);
     268                 :            :                         }
     269                 :            :                 }
     270                 :            : 
     271                 :          5 :                 *mem = NULL;
     272                 :            :         }
     273                 :          5 : }
     274                 :            : 
     275                 :            : void
     276                 :          0 : TR_cleanup()
     277                 :            : {
     278                 :            : #ifdef MEM_OPT
     279                 :            :         int i;
     280                 :            : 
     281                 :          0 :         for (i=0; i<TR_MAX_MEM_IDX; i++) {
     282                 :          0 :                 while(segments[i]) {
     283                 :          0 :                         struct memSegment * next = segments[i]->next;
     284                 :          0 :                         free(segments[i]);
     285                 :          0 :                         segments[i] = next;
     286                 :            :                 }
     287                 :            :         }
     288                 :            : #endif
     289                 :          0 : }
     290                 :            : 
     291                 :            : char *
     292                 :          0 : TR_strdup(const char * src)
     293                 :            : {
     294                 :            :         char * dup;
     295                 :            : 
     296                 :          0 :         if (NULL == src) {
     297                 :          0 :                 return NULL;
     298                 :            :         }
     299                 :            : 
     300                 :          0 :         dup = TR_malloc(strlen(src)+1);
     301                 :          0 :         strcpy(dup, src);
     302                 :            : 
     303                 :          0 :         return dup;
     304                 :            : }
     305                 :            : 
     306                 :            : // vim: set ts=4 sw=4:

Generated by: LCOV version 1.11