tarantool / small

Specialized memory allocators

small - a collection of Specialized Memory ALLocators for small allocations

The library provides the following facilities:

quota

Set a limit on the amount of memory all allocators use. Thread-safe.

slab_arena

To initialize an arena, you need a quota. Multiple arenas can use a shared quota object. Thread safe.

Defines an API with two methods: map() and unmap(). Map returns a memory area. Unmap returns this area to the arena. All objects returned by arena have the same size, defined in initialization-time constant SLAB_MAX_SIZE. By default, SLAB_MAX_SIZE is 4M. All objects returned by arena are aligned by SLAB_MAX_SIZE: (ptr & (SLAB_MAX_SIZE - 1)) is always 0. SLAB_MAX_SIZE therefore must be a power of 2. Limiting SLAB_MAX_SIZE is important to avoid internal fragmentation. Multiple arenas can exist, an object must be returned to the same arena in which it was allocated.

There is a number of different implementations of slab_arena API:

• huge_arena: this implementation maps at initialization time a huge region of memory, and then uses this region to produce objects. Can be configured to use shared or private mappings.
• grow_arena - mmaps() each individual block. Thus can incur fragmentation of the address space, but actually returns objects to the OS on unmap.

Use of instances of slab_arena is thread-safe: multiple threads can use the same arena.

slab_cache

Requires an arena for initialization, which works as a memory source for slab_cache. Returns power-of-two sized slabs, with size-aligned address. Uses a buddy system to deal with memory fragmentation. Is expected to be thread-local.

mempool

A memory pool for objects of the same size. Thread local. Requires a slab cache, which works as a source of memory. Automatically defines the optimal slab size, given the object size. Supports alloc() and free().

region

A typical region allocator. Very cheap allocation, but all memory can be freed at once only. Supports savepoints, i.e. an allocation point to which it can roll back, i.e. free all memory allocated after a savepoint. Uses slab_cache as a memory source.

small

A typical slab allocator. Built as a collection of mempool allocators, each mempool suited for a particular object size. Has stepped pools, i.e. pools for small objects up to 500 bytes, and factored pools, for larger objects. The difference between stepped and factored pools is that object size in stepped pools grows step by step, each next pool serving objects of prev_pool_object_size + 8. In factored pools a growth factor is used, i.e. given a factor of 1.1 and previous pool for objects of size up to 1000, next pool will serve objects in range 1001-1100. Since is based on mempool, uses slab_cache as a memory source.

ibuf

A typical input buffer, which could be seen as a memory allocator as well, which reallocates itself when it gets full. Uses slab_cache as a memory source.

obuf

Another implementation of an output buffer, which, for growth, instead of reallocation, used a collection of buffers, size of each next buffer in a collection twice the size the prevoius one. Uses slab_cache as a memory source.

matras

This is the best one. Memory Address Translating allocator. Only allows to allocate objects of size which is a power of two. Provides a 32-bit id for each allocated object. Supports multi-versioning for all allocated objects, i.e. it's possible to create a consistent read view of all allocated memory.

Uses slab_cache as a memory source.

small's Issues

Add Doxygen documentation

compare_exchange_strong should be weak in case of loops

Inside loops, a spurious version of compare_exchange_* should be used (compare_exchange_weak): on some architectures non-spurious (compare_exchange_strong) version requires overhead in implementation, but inside loops, spurious fail doesn't break correctness.

More precise quota manager

Current struct quota implementation round all values up to 1kb. That is enough for slab_cache, lsregion and other allocators. In order to implement tarantool/tarantool#2047, we need more precise quota.

Possible solutions:

1. Don't use atomic uint64_t for used | total value and store total separately. Of course, there is no way to check used < total atomically in this case, but total is not changed so often and I think we can make dirty reads
2. Implement struct quota_cache, which lease 1Kb chunks from parent struct quota.
3. Don't care about quota right now and implement a general-purpose allocator.

valgrind integration, red zones

• support red zones
• integrate alloc/free calls with valgrind, MARK_MEM_FREE/MARK_MEM_USED

region_reset does not reset usage to 0 as expected

As a result region_join(&region, 0) after reset will prepend garbage left in region slabs other than the first one. In parcular this is what src/http.c and src/lua/http.c of Tarantool 3.0.0-alpha1-16-g0e5a3cc21 do for region with headers.

There is a patch 67d7ab4 which seems to fix the issue but it does not make it into upstream.

Compilation fails on Alpine Linux

/usr/src/tarantool/src/lib/small/test/arena_mt.c:27:18: error: cast from pointer to integer of different size [-Werror=pointer-to-int-cast]
intptr_t seed = (unsigned int) pthread_self();

smalloc: fallback to slab_get()/malloc() for large allocations

Tarantool uses smalloc()/smfree() (the "small" allocator) for tuples. We want to support large tuples without changing arena->slab_size == memx_tuple_max_size (4Mb by default), by using system malloc() for such rare allocations.

tarantool/tarantool#2667

Release build warning

/home/ubuntu/tarantool/src/lib/small/small/slab_arena.c:220:9: warning: variable 'total' set but not used [-Wunused-but-set-variable]
        size_t total = 0;

build: unused variable warning on clang 15

<...>/small/test/lf_lifo.c:54:6: error: variable 'i' set but not used
    [-Werror,-Wunused-but-set-variable]
        int i = 0;

lsregion: fall back to malloc() for large allocations

Fix CMake warning

-- Detecting CXX compile features - done
CMake Deprecation Warning at third_party/small/CMakeLists.txt:2 (cmake_minimum_required):
  Compatibility with CMake < 2.8.12 will be removed from a future version of
  CMake.

  Update the VERSION argument <min> value or use a ...<max> suffix to tell
  CMake that the project does not need compatibility with older versions.

cmake version 3.18.4

small depends on exception.h

Reported by @alyapunov

There are a pair of functions with 'xc' postfix in small sub-module. That why "exeption.h" is included and the small depends on exceptions definition.

This dependency hinders usage of small submodule as a standalone project.

I beleive 'xc' functions must be moved to somewhere like 'small_xc.h' (and possibly 'small_xc.cc')

Allow to set custom function attributes in BPS tree

I want to add "static inline" to BPS tree declaration:

000000000044c50c T vy_mem_tree_approximate_count
000000000044b1a3 T vy_mem_tree_build
000000000044b0e9 T vy_mem_tree_create
00000000004537c8 T vy_mem_tree_delete
000000000044b81f T vy_mem_tree_destroy
000000000044ca02 T vy_mem_tree_find
00000000004536f6 T vy_mem_tree_insert
000000000044bcf0 T vy_mem_tree_invalid_iterator
000000000044bef9 T vy_mem_tree_iterator_are_equal
000000000044c9d4 T vy_mem_tree_iterator_destroy
000000000044c082 T vy_mem_tree_iterator_first
000000000044c979 T vy_mem_tree_iterator_freeze
000000000044c77d T vy_mem_tree_iterator_get_elem
000000000044bd4a T vy_mem_tree_iterator_is_invalid
000000000044c0e3 T vy_mem_tree_iterator_last
000000000044c7cf T vy_mem_tree_iterator_next
000000000044c8a8 T vy_mem_tree_iterator_prev
000000000044c144 T vy_mem_tree_lower_bound
000000000044b850 T vy_mem_tree_mem_used
000000000044b91e T vy_mem_tree_random
000000000044b83e T vy_mem_tree_size
000000000044c317 T vy_mem_tree_upper_bound

region_reset() leaks memory

region_reset() only marks the first block as free. There may be other blocks which are neither reset no returned to the slab cache. Better free all blocks except the first - that would be both fast for small amounts and safe for big ones.

NULL deference in matras

See line 359 and 363:

void
314matras_destroy_read_view(struct matras *m, struct matras_view *v)
315{
   1. Condition v != &m->head, taking true branch.
316        assert(v != &m->head);
   2. Condition !v->next_view, taking false branch.
317        if (!v->next_view)
318                return;
319        struct matras_view *next_view = v->next_view;
320        struct matras_view *prev_view = v->prev_view;
321        next_view->prev_view = prev_view;
   3. Condition prev_view, taking true branch.
322        if (prev_view)
323                prev_view->next_view = next_view;
324        v->next_view = 0;
325
   4. Condition v->block_count == 0, taking false branch.
326        if (v->block_count == 0)
327                return;
   5. Condition v->root == next_view->root, taking true branch.
   6. Condition next_view->block_count, taking false branch.
328        if (v->root == next_view->root && next_view->block_count)
329                return;
   7. Condition prev_view, taking true branch.
   8. Condition v->root == prev_view->root, taking false branch.
330        if (prev_view && v->root == prev_view->root && prev_view->block_count)
331                return;
332        void **extent1 = (void **)v->root;
333        void **extent1n = (void **) next_view->root;
334        void **extent1p = 0;
   9. Condition prev_view, taking true branch.
335        if (prev_view)
336                extent1p = (void **) prev_view->root;
337        matras_id_t step1 = m->mask1 + 1;
338        matras_id_t step2 = m->mask2 + 1;
339        matras_id_t i1 = 0, j1 = 0, i2, j2;
340        matras_id_t ptrs_in_ext = m->extent_size / (matras_id_t)sizeof(void *);
   10. Condition j1 < v->block_count, taking true branch.
   16. Condition j1 < v->block_count, taking true branch.
341        for (; j1 < v->block_count; i1++, j1 += step1) {
342                void **extent2 = (void **)extent1[i1];
343                void **extent2n = 0;
   17. assign_zero: Assigning: extent2p = NULL.
344                void **extent2p = 0;
   11. Condition next_view->block_count > j1, taking false branch.
   18. Condition next_view->block_count > j1, taking false branch.
345                if (next_view->block_count > j1) {
346                        if (extent1[i1] == extent1n[i1])
347                                continue;
348                        extent2n = (void **) extent1n[i1];
349                }
   12. Condition prev_view, taking true branch.
   13. Condition prev_view->block_count > j1, taking true branch.
   19. Condition prev_view, taking true branch.
   20. Condition prev_view->block_count > j1, taking false branch.
350                if (prev_view && prev_view->block_count > j1) {
   14. Condition extent1[i1] == extent1p[i1], taking true branch.
351                        if (extent1[i1] == extent1p[i1])
   15. Continuing loop.
352                                continue;
353                        extent2p = (void **) extent1p[i1];
354                }
   21. Condition i2 < ptrs_in_ext, taking true branch.
   22. Condition j1 + j2 < v->block_count, taking true branch.
   27. Condition i2 < ptrs_in_ext, taking true branch.
   28. Condition j1 + j2 < v->block_count, taking true branch.
355                for (i2 = j2 = 0;
356                     i2 < ptrs_in_ext && j1 + j2 < v->block_count;
357                     i2++, j2 += step2) {
358                        void **extent3 = (void **)extent2[i2];
   23. Condition next_view->block_count > j1 + j2, taking false branch.
   29. Condition next_view->block_count > j1 + j2, taking false branch.
359                        if (next_view->block_count > j1 + j2) {
   CID 1398748: Explicit null dereferenced (FORWARD_NULL) [select issue]
360                                if (extent2[i2] == extent2n[i2])
361                                        continue;
362                        }
   24. Condition prev_view, taking true branch.
   25. Condition prev_view->block_count > j1 + j2, taking false branch.
   30. Condition prev_view, taking true branch.
   31. Condition prev_view->block_count > j1 + j2, taking true branch.
363                        if (prev_view && prev_view->block_count > j1 + j2) {
   CID 1398732 (#1 of 1): Explicit null dereferenced (FORWARD_NULL)32. var_deref_op: Dereferencing null pointer extent2p.
364                                if (extent2[i2] == extent2p[i2])
365                                        continue;
366                        }
367                        matras_free_extent(m, extent3);
   26. Jumping back to the beginning of the loop.
368                }
369                matras_free_extent(m, extent2);
370        }
371        matras_free_extent(m, extent1);
372}

Found by Coverity.

Fix build warnings in perf/small.cc

When I build RelWithDebInfo I have the following errors (gcc 9.4):

/home/alyapunov/Work/tarantool/src/lib/small/perf/small.cc: In function ‘void generate_benchmark_args(benchmark::internal::Benchmark*)’:
/home/alyapunov/Work/tarantool/src/lib/small/perf/small.cc:268:10: warning: narrowing conversion of ‘size’ from ‘unsigned int’ to ‘int’ [-Wnarrowing]
  268 |          size, objsize_arr[j].size_min,
      |          ^~~~
/home/alyapunov/Work/tarantool/src/lib/small/perf/small.cc:268:10: warning: narrowing conversion of ‘size’ from ‘unsigned int’ to ‘int’ [-Wnarrowing]
/home/alyapunov/Work/tarantool/src/lib/small/perf/small.cc:268:31: warning: narrowing conversion of ‘objsize_arr.std::array<becnhmark_args, 2>::operator[](((std::array<becnhmark_args, 2>::size_type)j)).becnhmark_args::size_min’ from ‘unsigned int’ to ‘int’ [-Wnarrowing]
  268 |          size, objsize_arr[j].size_min,
/home/alyapunov/Work/tarantool/src/lib/small/perf/small.cc:268:31: warning: narrowing conversion of ‘objsize_arr.std::array<becnhmark_args, 2>::operator[](((std::array<becnhmark_args, 2>::size_type)j)).becnhmark_args::size_min’ from ‘unsigned int’ to ‘int’ [-Wnarrowing]
/home/alyapunov/Work/tarantool/src/lib/small/perf/small.cc:269:25: warning: narrowing conversion of ‘objsize_arr.std::array<becnhmark_args, 2>::operator[](((std::array<becnhmark_args, 2>::size_type)j)).becnhmark_args::size_max’ from ‘unsigned int’ to ‘int’ [-Wnarrowing]
  269 |          objsize_arr[j].size_max,
/home/alyapunov/Work/tarantool/src/lib/small/perf/small.cc:269:25: warning: narrowing conversion of ‘objsize_arr.std::array<becnhmark_args, 2>::operator[](((std::array<becnhmark_args, 2>::size_type)j)).becnhmark_args::size_max’ from ‘unsigned int’ to ‘int’ [-Wnarrowing]
[ 29%] Linking C static library libjson.a
/home/alyapunov/Work/tarantool/src/lib/small/perf/small.cc:270:25: warning: narrowing conversion of ‘objsize_arr.std::array<becnhmark_args, 2>::operator[](((std::array<becnhmark_args, 2>::size_type)j)).becnhmark_args::prealloc’ from ‘unsigned int’ to ‘int’ [-Wnarrowing]
  270 |          objsize_arr[j].prealloc,
/home/alyapunov/Work/tarantool/src/lib/small/perf/small.cc:270:25: warning: narrowing conversion of ‘objsize_arr.std::array<becnhmark_args, 2>::operator[](((std::array<becnhmark_args, 2>::size_type)j)).becnhmark_args::prealloc’ from ‘unsigned int’ to ‘int’ [-Wnarrowing]
/home/alyapunov/Work/tarantool/src/lib/small/perf/small.cc:271:25: warning: narrowing conversion of ‘objsize_arr.std::array<becnhmark_args, 2>::operator[](((std::array<becnhmark_args, 2>::size_type)j)).becnhmark_args::mask’ from ‘unsigned int’ to ‘int’ [-Wnarrowing]
  271 |          objsize_arr[j].mask,
/home/alyapunov/Work/tarantool/src/lib/small/perf/small.cc:271:25: warning: narrowing conversion of ‘objsize_arr.std::array<becnhmark_args, 2>::operator[](((std::array<becnhmark_args, 2>::size_type)j)).becnhmark_args::mask’ from ‘unsigned int’ to ‘int’ [-Wnarrowing]
/home/alyapunov/Work/tarantool/src/lib/small/perf/small.cc:272:10: warning: narrowing conversion of ‘k’ from ‘unsigned int’ to ‘int’ [-Wnarrowing]
  272 |          k
      |          ^
/home/alyapunov/Work/tarantool/src/lib/small/perf/small.cc:272:10: warning: narrowing conversion of ‘k’ from ‘unsigned int’ to ‘int’ [-Wnarrowing]

Return aligned pointers from region_alloc()

Please align all returned pointers at least for 8 bytes or even better for 16 bytes.

Unaligned access is inefficient or even forbidden on some platforms:

Program terminated with signal SIGBUS, Bus error.
#0  txn_write_to_wal (txn=0xb642002e) at /home/roman/tarantool/src/box/txn.cc:143
143                     req->rows[req->n_rows++] = stmt->row;
[Current thread is 1 (Thread 0xb6fca000 (LWP 15475))]
(gdb) bt
#0  txn_write_to_wal (txn=0xb642002e) at /home/roman/tarantool/src/box/txn.cc:143

Create a BLOB database on top of it

If I take it correctly, these set of utilities provides a way to manipulate chunks of memory very efficiently.

I've faced a need to efficiently store a huge amount of small (about 20 kB) images and give a read access to it by the web server, nginx for example.

The problem is that having too many plain files are bad for performance, even if proper multilevel directory structure is used.
On the other hand, nginx provides a sendfile functionality that makes file access very efficient.

So, my idea is to join many small image files into one huge file with gigabyte size and provide a way to address each individual file in it. Then an appropriate nginx module can be extended to use offset in the sendfile OS call.
As a result we would have best of two worlds: sendfile performance and low file handlers count to not hurt filesystem and memory.

I'm writing it there because I think that these utilities is a good base for such a general-purpose BLOB database, and because there are people with a huge database creation background that can estimate the value of this idea.

Thank you!

Crash in matras_touch in snapshot_daemon.test

(gdb) f 0
#0  matras_touch (m=0xa9b76e0, id=<optimized out>) at /home/buildslave/tarantool/src/lib/small/small/matras.c:411
411     void **extent2p = (void **) extent1p[n1];
(gdb) bt
#0  matras_touch (m=0xa9b76e0, id=<optimized out>) at /home/buildslave/tarantool/src/lib/small/small/matras.c:411
#1  0x00000000004901d8 in bps_tree_index_touch_block (id=0, tree=0xa9b76a0) at /home/buildslave/tarantool/src/lib/salad/bps_tree.h:1214
#2  bps_tree_index_insert_into_leaf (new_elem=0x7f7c838070, leaf_path_elem=<synthetic pointer>, tree=0xa9b76a0) at /home/buildslave/tarantool/src/lib/salad/bps_tree.h:2143
#3  bps_tree_index_process_insert_leaf (new_elem=0x7f7c838070, leaf_path_elem=<synthetic pointer>, tree=0xa9b76a0) at /home/buildslave/tarantool/src/lib/salad/bps_tree.h:3019
#4  bps_tree_index_insert (tree=tree@entry=0xa9b76a0, new_elem=new_elem@entry=0x7f7c838070, replaced=0x5df310 <lj_char_bits>, replaced@entry=0x7f838a0c78)
    at /home/buildslave/tarantool/src/lib/salad/bps_tree.h:4054
#5  0x000000000048f2f4 in MemtxTree::replace (this=0xa9b7680, old_tuple=0x0, new_tuple=0x7f7c838070, mode=(DUP_INSERT | DUP_REPLACE | unknown: 124))
    at /home/buildslave/tarantool/src/box/memtx_tree.cc:244
#6  0x000000000047a010 in memtx_replace_all_keys (txn=0x7f838c0040, space=0xa9b75a0, old_tuple=0x7f838c0040, new_tuple=0x7f7c838070, mode=(unknown: 2206862840))
    at /home/buildslave/tarantool/src/box/memtx_engine.cc:486
#7  0x0000000000479954 in MemtxSpace::executeReplace (this=0xa9b0070, txn=0x7f838c0040, space=0xa9b75a0, request=0x7f838a0d68) at /home/buildslave/tarantool/src/box/memtx_engine.cc:238
#8  0x0000000000455c28 in process_rw (result=0x7f838a0df8, request=0x7f838a0d68) at /home/buildslave/tarantool/src/box/box.cc:116
#9  box_process1 (request=0x7f838a0d68, request@entry=0x7f838a0d88, result=result@entry=0x7f838a0df8) at /home/buildslave/tarantool/src/box/box.cc:536
#10 0x00000000004561f4 in box_insert (space_id=space_id@entry=512, tuple=0x7f838c0038 "\221\002\002", tuple_end=0x7f838c003a "\002", result=0x7f838a0df8, result@entry=0x7f838a0e18)
    at /home/buildslave/tarantool/src/box/box.cc:576
#11 0x000000000046597c in lbox_insert (L=0x7f83eee7a8) at /home/buildslave/tarantool/src/box/lua/index.c:55
#12 0x000000000050ac64 in lj_BC_FUNCC () at buildvm_arm64.dasc:894
#13 0x00000000004f7f70 in lua_pcall (L=L@entry=0x7f83eee7a8, nargs=<optimized out>, nresults=nresults@entry=-1, errfunc=errfunc@entry=0) at lj_api.c:1055
#14 0x00000000004aae90 in box_lua_fiber_run (ap=...) at /home/buildslave/tarantool/src/lua/fiber.c:279

tarantool/tarantool#1185

No reference to 8ef2ec4b383e3b518fbfc462eee8d9c9786c3a64

Current master (2.8.0) is looking at commit 8ef2ec4, but the branch with that commit has already been deleted.

Centos6 build failed

CentOS 6 is completely removed on external resources. We were able to build the image using the archives on the Vault mirror sites, but we didn't find everything there. The condition gcc >= 4.5 in the small.spec is not perform

No reference to 2e8d1a0e84fb863f56a233f0925cb0eb18a52d6a

Tarantool versions from 1.7.3-344-gef7a02036 to 1.7.4-190-g5d09d2336 (exclusive) have the submodule src/lib/small refering to the commit 1. The commit now is not referenced by any branch or tag, so cannot be retrieved in usual ways.

How to see how it breaks things:

git clone [email protected]:tarantool/tarantool.git
cd tarantool
git checkout ef7a02036
git submodule update --recursive --init

It shows the following error:

error: Server does not allow request for unadvertised object 2e8d1a0e84fb863f56a233f0925cb0eb18a52d6a
Fetched in submodule path 'src/lib/small', but it did not contain 2e8d1a0e84fb863f56a233f0925cb0eb18a52d6a. Direct fetching of that commit failed.

I think it is good to promote a parent project long-term branches only to commits in subproject long-term branches. Across guarding from errors like one described above, this approach also provides some guarantees that a subproject commit will not be discarded during the submodule updating by a mistake.

Out of bounds access in mhash

Found by Coverity:

507int
508_mh(start_resize)(struct _mh(t) *h, mh_int_t buckets, mh_int_t batch,
509                  mh_arg_t arg)
510{
   1. Condition h->resize_position, taking false branch.
511        if (h->resize_position) {
512                /* resize has already been started */
513                return 0;
514        }
   2. Condition buckets < h->n_buckets, taking false branch.
515        if (buckets < h->n_buckets) {
516                /* hash size is already greater than requested */
517                return 0;
518        }
   3. Condition h->prime < 31, taking true branch.
   6. Condition h->prime < 31, taking true branch.
   9. Condition h->prime < 31, taking false branch.
   10. cond_const: Checking h->prime < 31U implies that h->prime is 31 on the false branch.
519        while (h->prime < __ac_HASH_PRIME_SIZE) {
   4. Condition __ac_prime_list[h->prime] >= buckets, taking false branch.
   7. Condition __ac_prime_list[h->prime] >= buckets, taking false branch.
520                if (__ac_prime_list[h->prime] >= buckets)
521                        break;
522                h->prime += 1;
   5. Jumping back to the beginning of the loop.
   8. Jumping back to the beginning of the loop.
523        }
524
   11. Condition batch > 0, taking true branch.
525        h->batch = batch > 0 ? batch : h->n_buckets / (256 * 1024);
   12. Condition h->batch < 256, taking true branch.
526        if (h->batch < 256) {
527                /*
528                 * Minimal batch must be greater or equal to
529                 * 1 / (1 - f), where f is upper bound percent
530                 * = MH_DENSITY
531                 */
532                h->batch = 256;
533        }
534
535        struct _mh(t) *s = h->shadow;
536        memcpy(s, h, sizeof(*h));
537        s->resize_position = 0;
   CID 1398773: Out-of-bounds read (OVERRUN) [select issue]
   CID 1398793: Out-of-bounds read (OVERRUN) [select issue]
   CID 1398769: Out-of-bounds read (OVERRUN) [select issue]
   CID 1398780: Out-of-bounds read (OVERRUN) [select issue]
   CID 1398776: Out-of-bounds read (OVERRUN) [select issue]
   CID 1398762 (#1 of 1): Out-of-bounds read (OVERRUN)13. overrun-local: Overrunning array __ac_prime_list of 31 4-byte elements at element index 31 (byte offset 124) using index h->prime (which evaluates to 31).
538        s->n_buckets = __ac_prime_list[h->prime];
539        s->upper_bound = s->n_buckets * MH_DENSITY;
540        s->n_dirty = 0;
541        s->size = 0;
542        s->p = (mh_node_t *) malloc(s->n_buckets * sizeof(mh_node_t));

No reference to cebc40574cb68a21dac16c438371392db8f98f66

small submodule in tarantool was mistakely (AFAIU) promoted to cebc405 commit, which is not on master, tarantool-2.1 tarantool-1.10 branch. It is on gerold103/gh-2971-symbols branch and when it'll disappear it will be not possible to checkout tarantool/tarantool@03790ac with submodules w/o an error. See #20 for description of the similar problem.

No reference to 086f51f0cc7cb3bf3f7879257bf9df296b5995f4

(For now there is the reference: avtikhon/osx_1.10 branch, but once it will be deleted it will disappear.)

tarantool's branch 1.10 looking into this commit. It is not in small's master, so will be unavailable when avtikhon/osx_1.10 will be deleted. We need to create a tag like gh-22-do-not-remove pointing to this commit.

See #20 for better description.

Support compilation with C89

As far as I got this change, the idea was to use parent's project CFLAGS when libsmall is built as part of another project (and so when CMake variable SMALL_EMBEDDED is set). So we should be quite tolerable to different options and C dialects.

GCC 4.8 comforms to C89 by default (with GNU extensions, as if -std=gnu90 would be passed). GCC 4.8 is the default compiler on Ubuntu Trusty that is the previous default OS on Travis CI (until it was changed to Xenial).

All those facts comes into one fail when we tried to update libsmall in tarantool/memcached module.

Please, ensure that C89 support will not break again with a CI rule.

Thanks @LeonidVas for the initial investigation.

store to misaligned address 0x7f0bd8088074 for type 'void *', which requires 8 byte alignment

Bug description:

[034] /builds/DtQXhC5e/0/tarantool/tarantool/src/lib/small/small/mempool.c:94:2: runtime error: store to misaligned address 0x7f0bd8088074 for type 'void *', which requires 8 byte alignment
[034] 0x7f0bd8088074: note: pointer points here
[034]   00 00 00 00 00 00 00 00  02 00 00 00 0a 00 91 01  70 80 08 d8 0b 7f 00 00  02 00 00 00 0a 80 91 02
[034]               ^ 
[034] SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior /builds/DtQXhC5e/0/tarantool/tarantool/src/lib/small/small/mempool.c:94:2 in 
[034] [ fail ]

https://gitlab.com/tarantool/tarantool/-/jobs/887050444

slab_get() bypasses quota accounting

Current implementation of slab_get() uses slab_map() to allocates sizes < slab_size (i.e. 4mb for runtime arena in Tarantool) and malloc() for huge sizes. In the first case quota is accounted by slab_map() function, in the second case quota is simple not accounted at all. The two major users of "malloc() via slab_get()" feature are ibuf and obuf. That means networks buffers (ibuf/obuf) in Tarantool are simple not accounted when size is >= slab_size. Since both buffers use exponential growing starting from some initial value (e.g. box.cfg.readahead = 16k in Tarantool), this situation are pretty common.

Please fix this problem by adding a pair of functions to slab_arena(), which can be used for huge allocations. Alternative way is to patch slab_map() to call mmap() directly for huge size. In all cases, slab_get() should be limited to accept aligned addresses only.

Make unit tests TAP-compliant

small has a set of unit test written with TAP framework - https://github.com/tarantool/small/tree/master/test

These unit tests produce a TAP output but it is not actually a TAP compliant and test-run.py cannot parse output from these tests. That's why we maintain .result files for unit tests and use diff-based approach here.

We need to fix output in a lib used in unit tests and make output from unit tests TAP compliant.

Same issue for tarantool tests - tarantool/tarantool#5000

mempool iterator

Implement an iterator over allocated (alive) mempool objects.