LCOV - code coverage report
Current view: top level - lib/os - heap.h (source / functions) Hit Total Coverage
Test: coverage.info Lines: 66 75 88.0 %
Date: 2022-08-18 11:36:24 Functions: 24 26 92.3 %
Legend: Lines: hit not hit | Branches: + taken - not taken # not executed Branches: 8 18 44.4 %

           Branch data     Line data    Source code
       1                 :            : /*
       2                 :            :  * Copyright (c) 2019 Intel Corporation
       3                 :            :  *
       4                 :            :  * SPDX-License-Identifier: Apache-2.0
       5                 :            :  */
       6                 :            : #ifndef ZEPHYR_INCLUDE_LIB_OS_HEAP_H_
       7                 :            : #define ZEPHYR_INCLUDE_LIB_OS_HEAP_H_
       8                 :            : 
       9                 :            : /*
      10                 :            :  * Internal heap APIs
      11                 :            :  */
      12                 :            : 
      13                 :            : /* Theese validation checks are non-trivially expensive, so enable
      14                 :            :  * only when debugging the heap code.  They shouldn't be routine
      15                 :            :  * assertions.
      16                 :            :  */
      17                 :            : #ifdef CONFIG_SYS_HEAP_VALIDATE
      18                 :            : #define CHECK(x) __ASSERT(x, "")
      19                 :            : #else
      20                 :            : #define CHECK(x) /**/
      21                 :            : #endif
      22                 :            : 
      23                 :            : /* Chunks are identified by their offset in 8 byte units from the
      24                 :            :  * first address in the buffer (a zero-valued chunkid_t is used as a
      25                 :            :  * null; that chunk would always point into the metadata at the start
      26                 :            :  * of the heap and cannot be allocated).  They are prefixed by a
      27                 :            :  * variable size header that depends on the size of the heap.  Heaps
      28                 :            :  * with fewer than 2^15 units (256kb) of storage use shorts to store
      29                 :            :  * the fields, otherwise the units are 32 bit integers for a 16Gb heap
      30                 :            :  * space (larger spaces really aren't in scope for this code, but
      31                 :            :  * could be handled similarly I suppose).  Because of that design
      32                 :            :  * there's a certain amount of boilerplate API needed to expose the
      33                 :            :  * field accessors since we can't use natural syntax.
      34                 :            :  *
      35                 :            :  * The fields are:
      36                 :            :  *   LEFT_SIZE: The size of the left (next lower chunk in memory)
      37                 :            :  *              neighbor chunk.
      38                 :            :  *   SIZE_AND_USED: the total size (including header) of the chunk in
      39                 :            :  *                  8-byte units.  The bottom bit stores a "used" flag.
      40                 :            :  *   FREE_PREV: Chunk ID of the previous node in a free list.
      41                 :            :  *   FREE_NEXT: Chunk ID of the next node in a free list.
      42                 :            :  *
      43                 :            :  * The free lists are circular lists, one for each power-of-two size
      44                 :            :  * category.  The free list pointers exist only for free chunks,
      45                 :            :  * obviously.  This memory is part of the user's buffer when
      46                 :            :  * allocated.
      47                 :            :  *
      48                 :            :  * The field order is so that allocated buffers are immediately bounded
      49                 :            :  * by SIZE_AND_USED of the current chunk at the bottom, and LEFT_SIZE of
      50                 :            :  * the following chunk at the top. This ordering allows for quick buffer
      51                 :            :  * overflow detection by testing left_chunk(c + chunk_size(c)) == c.
      52                 :            :  */
      53                 :            : 
      54                 :            : enum chunk_fields { LEFT_SIZE, SIZE_AND_USED, FREE_PREV, FREE_NEXT };
      55                 :            : 
      56                 :            : #define CHUNK_UNIT 8U
      57                 :            : 
      58                 :            : typedef struct { char bytes[CHUNK_UNIT]; } chunk_unit_t;
      59                 :            : 
      60                 :            : /* big_heap needs uint32_t, small_heap needs uint16_t */
      61                 :            : typedef uint32_t chunkid_t;
      62                 :            : typedef uint32_t chunksz_t;
      63                 :            : 
      64                 :            : struct z_heap_bucket {
      65                 :            :         chunkid_t next;
      66                 :            : };
      67                 :            : 
      68                 :            : struct z_heap {
      69                 :            :         chunkid_t chunk0_hdr[2];
      70                 :            :         chunkid_t end_chunk;
      71                 :            :         uint32_t avail_buckets;
      72                 :            : #ifdef CONFIG_SYS_HEAP_RUNTIME_STATS
      73                 :            :         size_t free_bytes;
      74                 :            :         size_t allocated_bytes;
      75                 :            :         size_t max_allocated_bytes;
      76                 :            : #endif
      77                 :            :         struct z_heap_bucket buckets[0];
      78                 :            : };
      79                 :            : 
      80                 :       3692 : static inline bool big_heap_chunks(chunksz_t chunks)
      81                 :            : {
      82                 :            :         if (IS_ENABLED(CONFIG_SYS_HEAP_SMALL_ONLY)) {
      83                 :            :                 return false;
      84                 :            :         }
      85                 :            :         if (IS_ENABLED(CONFIG_SYS_HEAP_BIG_ONLY) || sizeof(void *) > 4U) {
      86                 :            :                 return true;
      87                 :            :         }
      88                 :       3692 :         return chunks > 0x7fffU;
      89                 :            : }
      90                 :            : 
      91                 :          2 : static inline bool big_heap_bytes(size_t bytes)
      92                 :            : {
      93                 :          2 :         return big_heap_chunks(bytes / CHUNK_UNIT);
      94                 :            : }
      95                 :            : 
      96                 :       3690 : static inline bool big_heap(struct z_heap *h)
      97                 :            : {
      98                 :       3690 :         return big_heap_chunks(h->end_chunk);
      99                 :            : }
     100                 :            : 
     101                 :       2916 : static inline chunk_unit_t *chunk_buf(struct z_heap *h)
     102                 :            : {
     103                 :            :         /* the struct z_heap matches with the first chunk */
     104                 :       2916 :         return (chunk_unit_t *)h;
     105                 :            : }
     106                 :            : 
     107                 :       1708 : static inline chunkid_t chunk_field(struct z_heap *h, chunkid_t c,
     108                 :            :                                     enum chunk_fields f)
     109                 :            : {
     110                 :       1708 :         chunk_unit_t *buf = chunk_buf(h);
     111                 :       1708 :         void *cmem = &buf[c];
     112                 :            : 
     113         [ -  + ]:       1708 :         if (big_heap(h)) {
     114                 :          0 :                 return ((uint32_t *)cmem)[f];
     115                 :            :         } else {
     116                 :       1708 :                 return ((uint16_t *)cmem)[f];
     117                 :            :         }
     118                 :            : }
     119                 :            : 
     120                 :        864 : static inline void chunk_set(struct z_heap *h, chunkid_t c,
     121                 :            :                              enum chunk_fields f, chunkid_t val)
     122                 :            : {
     123                 :            :         CHECK(c <= h->end_chunk);
     124                 :            : 
     125                 :        864 :         chunk_unit_t *buf = chunk_buf(h);
     126                 :        864 :         void *cmem = &buf[c];
     127                 :            : 
     128         [ -  + ]:        864 :         if (big_heap(h)) {
     129                 :            :                 CHECK(val == (uint32_t)val);
     130                 :          0 :                 ((uint32_t *)cmem)[f] = val;
     131                 :            :         } else {
     132                 :            :                 CHECK(val == (uint16_t)val);
     133                 :        864 :                 ((uint16_t *)cmem)[f] = val;
     134                 :            :         }
     135                 :        864 : }
     136                 :            : 
     137                 :        255 : static inline bool chunk_used(struct z_heap *h, chunkid_t c)
     138                 :            : {
     139                 :        255 :         return chunk_field(h, c, SIZE_AND_USED) & 1U;
     140                 :            : }
     141                 :            : 
     142                 :       1112 : static inline chunksz_t chunk_size(struct z_heap *h, chunkid_t c)
     143                 :            : {
     144                 :       1112 :         return chunk_field(h, c, SIZE_AND_USED) >> 1;
     145                 :            : }
     146                 :            : 
     147                 :        173 : static inline void set_chunk_used(struct z_heap *h, chunkid_t c, bool used)
     148                 :            : {
     149                 :        173 :         chunk_unit_t *buf = chunk_buf(h);
     150                 :        173 :         void *cmem = &buf[c];
     151                 :            : 
     152         [ -  + ]:        173 :         if (big_heap(h)) {
     153         [ #  # ]:          0 :                 if (used) {
     154                 :          0 :                         ((uint32_t *)cmem)[SIZE_AND_USED] |= 1U;
     155                 :            :                 } else {
     156                 :          0 :                         ((uint32_t *)cmem)[SIZE_AND_USED] &= ~1U;
     157                 :            :                 }
     158                 :            :         } else {
     159         [ +  + ]:        173 :                 if (used) {
     160                 :         88 :                         ((uint16_t *)cmem)[SIZE_AND_USED] |= 1U;
     161                 :            :                 } else {
     162                 :         85 :                         ((uint16_t *)cmem)[SIZE_AND_USED] &= ~1U;
     163                 :            :                 }
     164                 :            :         }
     165                 :        173 : }
     166                 :            : 
     167                 :            : /*
     168                 :            :  * Note: no need to preserve the used bit here as the chunk is never in use
     169                 :            :  * when its size is modified, and potential set_chunk_used() is always
     170                 :            :  * invoked after set_chunk_size().
     171                 :            :  */
     172                 :        260 : static inline void set_chunk_size(struct z_heap *h, chunkid_t c, chunksz_t size)
     173                 :            : {
     174                 :        260 :         chunk_set(h, c, SIZE_AND_USED, size << 1);
     175                 :        260 : }
     176                 :            : 
     177                 :          0 : static inline chunkid_t prev_free_chunk(struct z_heap *h, chunkid_t c)
     178                 :            : {
     179                 :          0 :         return chunk_field(h, c, FREE_PREV);
     180                 :            : }
     181                 :            : 
     182                 :        171 : static inline chunkid_t next_free_chunk(struct z_heap *h, chunkid_t c)
     183                 :            : {
     184                 :        171 :         return chunk_field(h, c, FREE_NEXT);
     185                 :            : }
     186                 :            : 
     187                 :        172 : static inline void set_prev_free_chunk(struct z_heap *h, chunkid_t c,
     188                 :            :                                        chunkid_t prev)
     189                 :            : {
     190                 :        172 :         chunk_set(h, c, FREE_PREV, prev);
     191                 :        172 : }
     192                 :            : 
     193                 :        172 : static inline void set_next_free_chunk(struct z_heap *h, chunkid_t c,
     194                 :            :                                        chunkid_t next)
     195                 :            : {
     196                 :        172 :         chunk_set(h, c, FREE_NEXT, next);
     197                 :        172 : }
     198                 :            : 
     199                 :        170 : static inline chunkid_t left_chunk(struct z_heap *h, chunkid_t c)
     200                 :            : {
     201                 :        170 :         return c - chunk_field(h, c, LEFT_SIZE);
     202                 :            : }
     203                 :            : 
     204                 :        511 : static inline chunkid_t right_chunk(struct z_heap *h, chunkid_t c)
     205                 :            : {
     206                 :        511 :         return c + chunk_size(h, c);
     207                 :            : }
     208                 :            : 
     209                 :        260 : static inline void set_left_chunk_size(struct z_heap *h, chunkid_t c,
     210                 :            :                                        chunksz_t size)
     211                 :            : {
     212                 :        260 :         chunk_set(h, c, LEFT_SIZE, size);
     213                 :        260 : }
     214                 :            : 
     215                 :        257 : static inline bool solo_free_header(struct z_heap *h, chunkid_t c)
     216                 :            : {
     217   [ -  +  -  - ]:        257 :         return big_heap(h) && chunk_size(h, c) == 1U;
     218                 :            : }
     219                 :            : 
     220                 :        688 : static inline size_t chunk_header_bytes(struct z_heap *h)
     221                 :            : {
     222         [ -  + ]:        688 :         return big_heap(h) ? 8 : 4;
     223                 :            : }
     224                 :            : 
     225                 :          2 : static inline size_t heap_footer_bytes(size_t size)
     226                 :            : {
     227         [ -  + ]:          2 :         return big_heap_bytes(size) ? 8 : 4;
     228                 :            : }
     229                 :            : 
     230                 :        433 : static inline chunksz_t chunksz(size_t bytes)
     231                 :            : {
     232                 :        433 :         return (bytes + CHUNK_UNIT - 1U) / CHUNK_UNIT;
     233                 :            : }
     234                 :            : 
     235                 :        431 : static inline chunksz_t bytes_to_chunksz(struct z_heap *h, size_t bytes)
     236                 :            : {
     237                 :        431 :         return chunksz(chunk_header_bytes(h) + bytes);
     238                 :            : }
     239                 :            : 
     240                 :        345 : static inline chunksz_t min_chunk_size(struct z_heap *h)
     241                 :            : {
     242                 :        345 :         return bytes_to_chunksz(h, 1);
     243                 :            : }
     244                 :            : 
     245                 :          0 : static inline size_t chunksz_to_bytes(struct z_heap *h, chunksz_t chunksz_in)
     246                 :            : {
     247                 :          0 :         return chunksz_in * CHUNK_UNIT - chunk_header_bytes(h);
     248                 :            : }
     249                 :            : 
     250                 :        344 : static inline int bucket_idx(struct z_heap *h, chunksz_t sz)
     251                 :            : {
     252                 :        344 :         unsigned int usable_sz = sz - min_chunk_size(h) + 1;
     253                 :        344 :         return 31 - __builtin_clz(usable_sz);
     254                 :            : }
     255                 :            : 
     256                 :         86 : static inline bool size_too_big(struct z_heap *h, size_t bytes)
     257                 :            : {
     258                 :            :         /*
     259                 :            :          * Quick check to bail out early if size is too big.
     260                 :            :          * Also guards against potential arithmetic overflows elsewhere.
     261                 :            :          */
     262                 :         86 :         return (bytes / CHUNK_UNIT) >= h->end_chunk;
     263                 :            : }
     264                 :            : 
     265                 :            : /* For debugging */
     266                 :            : void heap_print_info(struct z_heap *h, bool dump_chunks);
     267                 :            : 
     268                 :            : #endif /* ZEPHYR_INCLUDE_LIB_OS_HEAP_H_ */

Generated by: LCOV version 1.14