pixalloc.c

Go to the documentation of this file.

/*====================================================================*
 -  Copyright (C) 2001 Leptonica.  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 COPYRIGHT HOLDERS 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 ANY
 -  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.
 *====================================================================*/

#include "allheaders.h"

/*-------------------------------------------------------------------------*
 *                          Pix Memory Storage                             *
 *                                                                         *
 *  This is a simple utility for handling pix memory storage.  It is       *
 *  enabled by setting the PixMemoryManager allocators to the functions    *
 *  that are defined here                                                  *
 *        pmsCustomAlloc()                                                 *
 *        pmsCustomDealloc()                                               *
 *  Use pmsCreate() at the beginning to do the pre-allocation, and         *
 *  pmsDestroy() at the end to clean it up.                                *
 *-------------------------------------------------------------------------*/
/*
 *  In the following, the "memory" refers to the image data
 *  field that is used within the pix.  The memory store is a
 *  continuous block of memory, that is logically divided into
 *  smaller "chunks" starting with a set at a minimum size, and
 *  followed by sets of increasing size that are a power of 2 larger
 *  than the minimum size.  You must specify the number of chunks
 *  of each size.
 *
 *  A requested data chunk, if it exists, is borrowed from the memory
 *  storage, and returned after use.  If the chunk is too small, or
 *  too large, or if all chunks in the appropriate size range are
 *  in use, the memory is allocated dynamically and freed after use.
 *
 *  There are four parameters that determine the use of pre-allocated memory:
 *
 *    minsize: any requested chunk smaller than this is allocated
 *             dynamically and destroyed after use.  No preallocated
 *             memory is used.
 *    smallest: the size of the smallest pre-allocated memory chunk.
 *    nlevels:  the number of different sizes of data chunks, each a
 *              power of 2 larger than 'smallest'.
 *    numalloc: a Numa of size 'nlevels' containing the number of data
 *              chunks for each size that are in the memory store.
 *
 *  As an example, suppose:
 *    minsize = 0.5MB
 *    smallest = 1.0MB
 *    nlevels = 4
 *    numalloc = {10, 5, 5, 5}
 *  Then the total amount of allocated memory (in MB) is
 *    10 * 1 + 5 * 2 + 5 * 4 + 5 * 8 = 80 MB
 *  Any pix requiring less than 0.5 MB or more than 8 MB of memory will
 *  not come from the memory store.  Instead, it will be dynamically
 *  allocated and freed after use.
 *
 *  How is this implemented?
 *
 *  At setup, the full data block size is computed and allocated.
 *  The addresses of the individual chunks are found, and the pointers
 *  are stored in a set of Ptra (generic pointer arrays), using one Ptra
 *  for each of the sizes of the chunks.  When returning a chunk after
 *  use, it is necessary to determine from the address which size level
 *  (ptra) the chunk belongs to.  This is done by comparing the address
 *  of the associated chunk.
 *
 *  In the event that memory chunks need to be dynamically allocated,
 *  either (1) because they are too small or too large for the memory
 *  store or (2) because all the pix of that size (i.e., in the
 *  appropriate level) in the memory store are in use, the
 *  addresses generated will be outside the pre-allocated block.
 *  After use they won't be returned to a ptra; instead the deallocator
 *  will free them.
 */

struct PixMemoryStore
{
    struct L_Ptraa  *paa;        
    size_t           minsize;    
    size_t           smallest;   
    size_t           largest;    
    size_t           nbytes;     
    l_int32          nlevels;    
    size_t          *sizes;      
    l_int32         *allocarray; 
    l_uint32        *baseptr;    
    l_uint32        *maxptr;     
    l_uint32       **firstptr;   
    l_int32         *memused;    
    l_int32         *meminuse;   
    l_int32         *memmax;     
    l_int32         *memempty;   
    char            *logfile;    
};
typedef struct PixMemoryStore   L_PIX_MEM_STORE;

static L_PIX_MEM_STORE  *CustomPMS = NULL;


l_ok
pmsCreate(size_t       minsize,
          size_t       smallest,
          NUMA        *numalloc,
          const char  *logfile)
{
l_int32           nlevels, i, j, nbytes;
l_int32          *alloca;
l_float32         nchunks;
l_uint32         *baseptr, *data;
l_uint32        **firstptr;
size_t           *sizes;
L_PIX_MEM_STORE  *pms;
L_PTRA           *pa;
L_PTRAA          *paa;

    PROCNAME("createPMS");

    if (!numalloc)
        return ERROR_INT("numalloc not defined", procName, 1);
    numaGetSum(numalloc, &nchunks);
    if (nchunks > 1000.0)
        L_WARNING("There are %.0f chunks\n", procName, nchunks);

    if ((pms = (L_PIX_MEM_STORE *)LEPT_CALLOC(1, sizeof(L_PIX_MEM_STORE)))
        == NULL)
        return ERROR_INT("pms not made", procName, 1);
    CustomPMS = pms;

        /* Make sure that minsize and smallest are multiples of 32 bit words */
    if (minsize % 4 != 0)
        minsize -= minsize % 4;
    pms->minsize = minsize;
    nlevels = numaGetCount(numalloc);
    pms->nlevels = nlevels;

    if ((sizes = (size_t *)LEPT_CALLOC(nlevels, sizeof(size_t))) == NULL)
        return ERROR_INT("sizes not made", procName, 1);
    pms->sizes = sizes;
    if (smallest % 4 != 0)
        smallest += 4 - (smallest % 4);
    pms->smallest = smallest;
    for (i = 0; i < nlevels; i++)
        sizes[i] = smallest * (1 << i);
    pms->largest = sizes[nlevels - 1];

    alloca = numaGetIArray(numalloc);
    pms->allocarray = alloca;
    if ((paa = ptraaCreate(nlevels)) == NULL)
        return ERROR_INT("paa not made", procName, 1);
    pms->paa = paa;

    for (i = 0, nbytes = 0; i < nlevels; i++)
        nbytes += alloca[i] * sizes[i];
    pms->nbytes = nbytes;

    if ((baseptr = (l_uint32 *)LEPT_CALLOC(nbytes / 4, sizeof(l_uint32)))
        == NULL)
        return ERROR_INT("calloc fail for baseptr", procName, 1);
    pms->baseptr = baseptr;
    pms->maxptr = baseptr + nbytes / 4;  /* just beyond the memory store */
    if ((firstptr = (l_uint32 **)LEPT_CALLOC(nlevels, sizeof(l_uint32 *)))
        == NULL)
        return ERROR_INT("calloc fail for firstptr", procName, 1);
    pms->firstptr = firstptr;

    data = baseptr;
    for (i = 0; i < nlevels; i++) {
        if ((pa = ptraCreate(alloca[i])) == NULL)
            return ERROR_INT("pa not made", procName, 1);
        ptraaInsertPtra(paa, i, pa);
        firstptr[i] = data;
        for (j = 0; j < alloca[i]; j++) {
            ptraAdd(pa, data);
            data += sizes[i] / 4;
        }
    }

    if (logfile) {
        pms->memused = (l_int32 *)LEPT_CALLOC(nlevels, sizeof(l_int32));
        pms->meminuse = (l_int32 *)LEPT_CALLOC(nlevels, sizeof(l_int32));
        pms->memmax = (l_int32 *)LEPT_CALLOC(nlevels, sizeof(l_int32));
        pms->memempty = (l_int32 *)LEPT_CALLOC(nlevels, sizeof(l_int32));
        pms->logfile = stringNew(logfile);
    }

    return 0;
}


void
pmsDestroy()
{
L_PIX_MEM_STORE  *pms;

    if ((pms = CustomPMS) == NULL)
        return;

    ptraaDestroy(&pms->paa, FALSE, FALSE);  /* don't touch the ptrs */
    LEPT_FREE(pms->baseptr);  /* free the memory */

    if (pms->logfile) {
        pmsLogInfo();
        LEPT_FREE(pms->logfile);
        LEPT_FREE(pms->memused);
        LEPT_FREE(pms->meminuse);
        LEPT_FREE(pms->memmax);
        LEPT_FREE(pms->memempty);
    }

    LEPT_FREE(pms->sizes);
    LEPT_FREE(pms->allocarray);
    LEPT_FREE(pms->firstptr);
    LEPT_FREE(pms);
    CustomPMS = NULL;
    return;
}


void *
pmsCustomAlloc(size_t  nbytes)
{
l_int32           level;
void             *data;
L_PIX_MEM_STORE  *pms;
L_PTRA           *pa;

    PROCNAME("pmsCustomAlloc");

    if ((pms = CustomPMS) == NULL)
        return (void *)ERROR_PTR("pms not defined", procName, NULL);

    pmsGetLevelForAlloc(nbytes, &level);

    if (level < 0) {  /* size range invalid; must alloc */
        if ((data = pmsGetAlloc(nbytes)) == NULL)
            return (void *)ERROR_PTR("data not made", procName, NULL);
    } else {  /* get from store */
        pa = ptraaGetPtra(pms->paa, level, L_HANDLE_ONLY);
        data = ptraRemoveLast(pa);
        if (data && pms->logfile) {
            pms->memused[level]++;
            pms->meminuse[level]++;
            if (pms->meminuse[level] > pms->memmax[level])
                pms->memmax[level]++;
        }
        if (!data) {  /* none left at this level */
            data = pmsGetAlloc(nbytes);
            if (pms->logfile)
                pms->memempty[level]++;
        }
    }

    return data;
}


void
pmsCustomDealloc(void  *data)
{
l_int32           level;
L_PIX_MEM_STORE  *pms;
L_PTRA           *pa;

    PROCNAME("pmsCustomDealloc");

    if ((pms = CustomPMS) == NULL) {
        L_ERROR("pms not defined\n", procName);
        return;
    }

    if (pmsGetLevelForDealloc(data, &level) == 1) {
        L_ERROR("level not found\n", procName);
        return;
    }

    if (level < 0) {  /* no logging; just free the data */
        LEPT_FREE(data);
    } else {  /* return the data to the store */
        pa = ptraaGetPtra(pms->paa, level, L_HANDLE_ONLY);
        ptraAdd(pa, data);
        if (pms->logfile)
            pms->meminuse[level]--;
    }

    return;
}


void *
pmsGetAlloc(size_t  nbytes)
{
void             *data;
FILE             *fp;
L_PIX_MEM_STORE  *pms;

    PROCNAME("pmsGetAlloc");

    if ((pms = CustomPMS) == NULL)
        return (void *)ERROR_PTR("pms not defined", procName, NULL);

    if ((data = (void *)LEPT_CALLOC(nbytes, sizeof(char))) == NULL)
        return (void *)ERROR_PTR("data not made", procName, NULL);
    if (pms->logfile && nbytes >= pms->smallest) {
        fp = fopenWriteStream(pms->logfile, "a");
        fprintf(fp, "Alloc %lu bytes at %p\n", (unsigned long)nbytes, data);
        fclose(fp);
    }

    return data;
}


l_ok
pmsGetLevelForAlloc(size_t    nbytes,
                    l_int32  *plevel)
{
l_int32           i;
l_float64         ratio;
L_PIX_MEM_STORE  *pms;

    PROCNAME("pmsGetLevelForAlloc");

    if (!plevel)
        return ERROR_INT("&level not defined", procName, 1);
    *plevel = -1;
    if ((pms = CustomPMS) == NULL)
        return ERROR_INT("pms not defined", procName, 1);

    if (nbytes < pms->minsize || nbytes > pms->largest)
        return 0;   /*  -1  */

    ratio = (l_float64)nbytes / (l_float64)(pms->smallest);
    for (i = 0; i < pms->nlevels; i++) {
        if (ratio <= 1.0)
            break;
        ratio /= 2.0;
    }
    *plevel = i;

    return 0;
}


l_ok
pmsGetLevelForDealloc(void     *data,
                      l_int32  *plevel)
{
l_int32           i;
l_uint32         *first;
L_PIX_MEM_STORE  *pms;

    PROCNAME("pmsGetLevelForDealloc");

    if (!plevel)
        return ERROR_INT("&level not defined", procName, 1);
    *plevel = -1;
    if (!data)
        return ERROR_INT("data not defined", procName, 1);
    if ((pms = CustomPMS) == NULL)
        return ERROR_INT("pms not defined", procName, 1);

    if (data < (void *)pms->baseptr || data >= (void *)pms->maxptr)
        return 0;   /*  -1  */

    for (i = 1; i < pms->nlevels; i++) {
        first = pms->firstptr[i];
        if (data < (void *)first)
            break;
    }
    *plevel = i - 1;

    return 0;
}


void
pmsLogInfo()
{
l_int32           i;
L_PIX_MEM_STORE  *pms;

    if ((pms = CustomPMS) == NULL)
        return;

    fprintf(stderr, "Total number of pix used at each level\n");
    for (i = 0; i < pms->nlevels; i++)
         fprintf(stderr, " Level %d (%lu bytes): %d\n", i,
                 (unsigned long)pms->sizes[i], pms->memused[i]);

    fprintf(stderr, "Max number of pix in use at any time in each level\n");
    for (i = 0; i < pms->nlevels; i++)
         fprintf(stderr, " Level %d (%lu bytes): %d\n", i,
                 (unsigned long)pms->sizes[i], pms->memmax[i]);

    fprintf(stderr, "Number of pix alloc'd because none were available\n");
    for (i = 0; i < pms->nlevels; i++)
         fprintf(stderr, " Level %d (%lu bytes): %d\n", i,
                 (unsigned long)pms->sizes[i], pms->memempty[i]);

    return;
}