path: root/leptonica/src/pixalloc.c

/*====================================================================*
 -  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.
 *====================================================================*/

/*!
 * \file pixalloc.c
 * <pre>
 *
 *      Custom memory storage with allocator and deallocator
 *
 *          l_int32       pmsCreate()
 *          void          pmsDestroy()
 *          void         *pmsCustomAlloc()
 *          void          pmsCustomDealloc()
 *          void         *pmsGetAlloc()
 *          l_int32       pmsGetLevelForAlloc()
 *          l_int32       pmsGetLevelForDealloc()
 *          void          pmsLogInfo()
 * </pre>
 */

#ifdef HAVE_CONFIG_H
#include <config_auto.h>
#endif  /* HAVE_CONFIG_H */

#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.
 */

/*! Pix memory storage */
struct PixMemoryStore
{
    struct L_Ptraa  *paa;        /*!< Holds ptrs to allocated memory        */
    size_t           minsize;    /*!< Pix smaller than this (in bytes)      */
                                 /*!< are allocated dynamically             */
    size_t           smallest;   /*!< Smallest mem (in bytes) alloc'd       */
    size_t           largest;    /*!< Larest mem (in bytes) alloc'd         */
    size_t           nbytes;     /*!< Size of allocated block w/ all chunks */
    l_int32          nlevels;    /*!< Num of power-of-2 sizes pre-alloc'd   */
    size_t          *sizes;      /*!< Mem sizes at each power-of-2 level    */
    l_int32         *allocarray; /*!< Number of mem alloc'd at each size    */
    l_uint32        *baseptr;    /*!< ptr to allocated array                */
    l_uint32        *maxptr;     /*!< ptr just beyond allocated memory      */
    l_uint32       **firstptr;   /*!< array of ptrs to first chunk in size  */
    l_int32         *memused;    /*!< log: total # of pix used (by level)   */
    l_int32         *meminuse;   /*!< log: # of pix in use (by level)       */
    l_int32         *memmax;     /*!< log: max # of pix in use (by level)   */
    l_int32         *memempty;   /*!< log: # of pix alloc'd because         */
                                 /*!<      the store was empty (by level)   */
    char            *logfile;    /*!< log: set to null if no logging        */
};
typedef struct PixMemoryStore   L_PIX_MEM_STORE;

static L_PIX_MEM_STORE  *CustomPMS = NULL;


/*!
 * \brief   pmsCreate()
 *
 * \param[in]    minsize    of data chunk that can be supplied by pms
 * \param[in]    smallest   bytes of the smallest pre-allocated data chunk.
 * \param[in]    numalloc   array with the number of data chunks for each
 *                          size that are in the memory store
 * \param[in]    logfile    use for debugging; null otherwise
 * \return  0 if OK, 1 on error
 *
 * <pre>
 * Notes:
 *      (1) This computes the size of the block of memory required
 *          and allocates it.  Each chunk starts on a 32-bit word boundary.
 *          The chunk sizes are in powers of 2, starting at %smallest,
 *          and the number of levels and chunks at each level is
 *          specified by %numalloc.
 *      (2) This is intended to manage the image data for a small number
 *          of relatively large pix.  The system malloc is expected to
 *          handle very large numbers of small chunks efficiently.
 *      (3) Important: set the allocators and call this function
 *          before any pix have been allocated.  Destroy all the pix
 *          in the normal way before calling pmsDestroy().
 *      (4) The pms struct is stored in a static global, so this function
 *          is not thread-safe.  When used, there must be only one thread
 *          per process.
 * </pre>
 */
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);

    pms = (L_PIX_MEM_STORE *)LEPT_CALLOC(1, sizeof(L_PIX_MEM_STORE));
    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;
}


/*!
 * \brief   pmsDestroy()
 *
 * <pre>
 * Notes:
 *      (1) Important: call this function at the end of the program, after
 *          the last pix has been destroyed.
 * </pre>
 */
void
pmsDestroy(void)
{
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;
}


/*!
 * \brief   pmsCustomAlloc()
 *
 * \param[in]   nbytes    min number of bytes in the chunk to be retrieved
 * \return  data ptr to chunk
 *
 * <pre>
 * Notes:
 *      (1) This attempts to find a suitable pre-allocated chunk.
 *          If not found, it dynamically allocates the chunk.
 *      (2) If logging is turned on, the allocations that are not taken
 *          from the memory store, and are at least as large as the
 *          minimum size the store can handle, are logged to file.
 * </pre>
 */
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;
}


/*!
 * \brief   pmsCustomDealloc()
 *
 * \param[in]   data    to be freed or returned to the storage
 * \return  void
 */
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]--;
    }
}


/*!
 * \brief   pmsGetAlloc()
 *
 * \param[in]    nbytes
 * \return  data
 *
 * <pre>
 * Notes:
 *      (1) This is called when a request for pix data cannot be
 *          obtained from the preallocated memory store.  After use it
 *          is freed like normal memory.
 *      (2) If logging is on, only write out allocs that are as large as
 *          the minimum size handled by the memory store.
 *      (3) The C99 platform-independent format specifier for size_t is %zu.
 *          Windows since at least VC-2015 is conforming; we can now use %zu.
 * </pre>
 */
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) {
        if ((fp = fopenWriteStream(pms->logfile, "a")) != NULL) {
            fprintf(fp, "Alloc %zu bytes at %p\n", nbytes, data);
            fclose(fp);
        } else {
            L_ERROR("failed to open stream for %s\n", procName, pms->logfile); 
        }
    }
    return data;
}


/*!
 * \brief   pmsGetLevelForAlloc()
 *
 * \param[in]   nbytes min number of bytes in the chunk to be retrieved
 * \param[out]  plevel  -1 if either too small or too large
 * \return  0 if OK, 1 on error
 */
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;
}


/*!
 * \brief   pmsGetLevelForDealloc()
 *
 * \param[in]   data ptr to memory chunk
 * \param[out]  plevel level in memory store; -1 if allocated
 *                     outside the store
 * \return  0 if OK, 1 on error
 */
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;
}


/*!
 * \brief   pmsLogInfo()
 */
void
pmsLogInfo(void)
{
l_int32           i;
L_PIX_MEM_STORE  *pms;

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

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

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

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