cpukit/libdl/rtl-bit-alloc.c

0001 /* SPDX-License-Identifier: BSD-2-Clause */
0002
0003 /**
0004  * @file
0005  *
0006  * @ingroup rtems_rtld
0007  *
0008  * @brief RTEMS Run-Time Link Editor Bit Allocator
0009  *
0010  * A configurable allocator for small peices of memory where embedding
0011  * control blocks into the memory are not viable. The amount of memory
0012  * should be small and the minimum allocator a 32bit work or higher.
0013  */
0014
0015 /*
0016  *  COPYRIGHT (c) 2019 Chris Johns <chrisj@rtems.org>
0017  *
0018  * Redistribution and use in source and binary forms, with or without
0019  * modification, are permitted provided that the following conditions
0020  * are met:
0021  * 1. Redistributions of source code must retain the above copyright
0022  *    notice, this list of conditions and the following disclaimer.
0023  * 2. Redistributions in binary form must reproduce the above copyright
0024  *    notice, this list of conditions and the following disclaimer in the
0025  *    documentation and/or other materials provided with the distribution.
0026  *
0027  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
0028  * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
0029  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
0030  * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
0031  * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
0032  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
0033  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
0034  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
0035  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
0036  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
0037  * POSSIBILITY OF SUCH DAMAGE.
0038  */
0039
0040 #ifdef HAVE_CONFIG_H
0041 #include "config.h"
0042 #endif
0043
0044 #include <errno.h>
0045 #include <inttypes.h>
0046 #include <stdio.h>
0047 #include <string.h>
0048
0049 #include <rtems/rtl/rtl-allocator.h>
0050 #include "rtl-bit-alloc.h"
0051 #include "rtl-error.h"
0052 #include <rtems/rtl/rtl-trace.h>
0053
0054 #define BITS_PER_WORD (sizeof (uint32_t) * 8)
0055
0056 static size_t
0057 bit_blocks (rtems_rtl_bit_alloc* balloc, size_t size)
0058 {
0059   if (size == 0)
0060     return 0;
0061   return ((size - 1) / balloc->block_size) + 1;
0062 }
0063
0064 static size_t
0065 bit_word (size_t bit)
0066 {
0067   return bit / BITS_PER_WORD;
0068 }
0069
0070 static size_t
0071 bit_offset (size_t bit)
0072 {
0073   return bit % (sizeof (uint32_t) * 8);
0074 }
0075
0076 static uint32_t
0077 bit_mask (size_t bit)
0078 {
0079   return 1 << bit_offset (bit);
0080 }
0081
0082 static void
0083 bit_set (rtems_rtl_bit_alloc* balloc, size_t start, size_t bits)
0084 {
0085   size_t b;
0086   for (b = start; b < (start + bits); ++b)
0087     balloc->bits[bit_word (b)] |= bit_mask (b);
0088 }
0089
0090 static void
0091 bit_clear (rtems_rtl_bit_alloc* balloc, size_t start, size_t bits)
0092 {
0093   size_t b;
0094   for (b = start; b < (start + bits); ++b)
0095     balloc->bits[bit_word (b)] &= ~bit_mask (b);
0096 }
0097
0098 static ssize_t
0099 bit_find_clear (rtems_rtl_bit_alloc* balloc, size_t blocks)
0100 {
0101   size_t base = 0;
0102   size_t clear = 0;
0103   size_t b;
0104
0105   for (b = 0; b < balloc->blocks; ++b)
0106   {
0107     if (balloc->bits[b] != 0xffffffff)
0108     {
0109       uint32_t word = balloc->bits[b];
0110       size_t   o;
0111       for (o = 0; o < BITS_PER_WORD; ++o, word >>= 1)
0112       {
0113         if ((word & 1) == 0)
0114         {
0115           if (clear == 0)
0116             base = (b * BITS_PER_WORD) + o;
0117           ++clear;
0118           if (clear == blocks)
0119             return base;
0120         }
0121         else
0122         {
0123           clear = 0;
0124           base = 0;
0125         }
0126       }
0127     }
0128     else
0129     {
0130       clear = 0;
0131       base = 0;
0132     }
0133   }
0134
0135   return -1;
0136 }
0137
0138 rtems_rtl_bit_alloc*
0139 rtems_rtl_bit_alloc_open (void* base, size_t size, size_t block_size, size_t used)
0140 {
0141   rtems_rtl_bit_alloc* balloc;
0142   const size_t         base_size = base == NULL ? size : 0;;
0143   const size_t         blocks = (size / block_size) / BITS_PER_WORD;
0144   const size_t         bit_bytes = blocks * sizeof(uint32_t);
0145
0146   if (rtems_rtl_trace (RTEMS_RTL_TRACE_BIT_ALLOC))
0147     printf ("rtl: balloc: open: base=%p size=%zu" \
0148             " block-size=%zu blocks=%zu used=%zu\n",
0149             base, size, block_size, blocks, used);
0150
0151   if (size == 0)
0152   {
0153     rtems_rtl_set_error (ENOMEM, "bit allocator size is 0");
0154     return false;
0155   }
0156
0157   if (used > size)
0158   {
0159     rtems_rtl_set_error (ENOMEM, "bad bit allocator used value");
0160     return false;
0161   }
0162
0163   balloc = rtems_rtl_alloc_new (RTEMS_RTL_ALLOC_OBJECT,
0164                                 sizeof (rtems_rtl_bit_alloc) + bit_bytes + base_size,
0165                                 true);
0166   if (balloc == NULL)
0167   {
0168     rtems_rtl_set_error (ENOMEM, "not bit allocator memory");
0169     return NULL;
0170   }
0171
0172   balloc->base =
0173     base == NULL ? ((void*) balloc) + sizeof (rtems_rtl_bit_alloc) + bit_bytes: base;
0174   balloc->size = size;
0175   balloc->bits = ((void*) balloc) + sizeof (rtems_rtl_bit_alloc);
0176   balloc->block_size = block_size;
0177   balloc->blocks = blocks;
0178
0179   bit_set (balloc, 0, bit_blocks (balloc, used));
0180
0181   return balloc;
0182 }
0183
0184 void
0185 rtems_rtl_bit_alloc_close (rtems_rtl_bit_alloc* balloc)
0186 {
0187   if (rtems_rtl_trace (RTEMS_RTL_TRACE_BIT_ALLOC))
0188     printf ("rtl: balloc: close: base=%p size=%zu\n",
0189             balloc->base, balloc->size);
0190   rtems_rtl_alloc_del (RTEMS_RTL_ALLOC_OBJECT, balloc);
0191 }
0192
0193 void*
0194 rtems_rtl_bit_alloc_balloc (rtems_rtl_bit_alloc* balloc, size_t size)
0195 {
0196   size_t  blocks = bit_blocks (balloc, size);
0197   ssize_t block = bit_find_clear (balloc, blocks);
0198   if (block < 0)
0199     return NULL;
0200   if (rtems_rtl_trace (RTEMS_RTL_TRACE_BIT_ALLOC))
0201     printf ("rtl: balloc: balloc: size=%zu blocks=%zu block=%zi\n",
0202             size, blocks, block);
0203   bit_set (balloc, block, blocks);
0204   return (void*) (balloc->base + (block * balloc->block_size));
0205 }
0206
0207 void
0208 rtems_rtl_bit_alloc_bfree (rtems_rtl_bit_alloc* balloc, void* addr, size_t size)
0209 {
0210   const uint8_t* a = (const uint8_t*) addr;
0211   if (addr != NULL && a >= balloc->base && a < balloc->base + balloc->size)
0212   {
0213     size_t block = bit_blocks (balloc, a - balloc->base);
0214     size_t blocks = bit_blocks (balloc, size);
0215     bit_clear (balloc, block, blocks);
0216   }
0217 }