1 //==- llvm/Support/ArrayRecycler.h - Recycling of Arrays ---------*- C++ -*-==//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 // This file defines the ArrayRecycler class template which can recycle small
10 // arrays allocated from one of the allocators in Allocator.h
11 //
12 //===----------------------------------------------------------------------===//
13 
14 #ifndef LLVM_SUPPORT_ARRAYRECYCLER_H
15 #define LLVM_SUPPORT_ARRAYRECYCLER_H
16 
17 #include "llvm/ADT/SmallVector.h"
18 #include "llvm/Support/Allocator.h"
19 #include "llvm/Support/MathExtras.h"
20 
21 namespace llvm {
22 
23 /// Recycle small arrays allocated from a BumpPtrAllocator.
24 ///
25 /// Arrays are allocated in a small number of fixed sizes. For each supported
26 /// array size, the ArrayRecycler keeps a free list of available arrays.
27 ///
28 template <class T, size_t Align = alignof(T)> class ArrayRecycler {
29   // The free list for a given array size is a simple singly linked list.
30   // We can't use iplist or Recycler here since those classes can't be copied.
31   struct FreeList {
32     FreeList *Next;
33   };
34 
35   static_assert(Align >= alignof(FreeList), "Object underaligned");
36   static_assert(sizeof(T) >= sizeof(FreeList), "Objects are too small");
37 
38   // Keep a free list for each array size.
39   SmallVector<FreeList*, 8> Bucket;
40 
41   // Remove an entry from the free list in Bucket[Idx] and return it.
42   // Return NULL if no entries are available.
pop(unsigned Idx)43   T *pop(unsigned Idx) {
44     if (Idx >= Bucket.size())
45       return nullptr;
46     FreeList *Entry = Bucket[Idx];
47     if (!Entry)
48       return nullptr;
49     __asan_unpoison_memory_region(Entry, Capacity::get(Idx).getSize());
50     Bucket[Idx] = Entry->Next;
51     __msan_allocated_memory(Entry, Capacity::get(Idx).getSize());
52     return reinterpret_cast<T*>(Entry);
53   }
54 
55   // Add an entry to the free list at Bucket[Idx].
push(unsigned Idx,T * Ptr)56   void push(unsigned Idx, T *Ptr) {
57     assert(Ptr && "Cannot recycle NULL pointer");
58     FreeList *Entry = reinterpret_cast<FreeList*>(Ptr);
59     if (Idx >= Bucket.size())
60       Bucket.resize(size_t(Idx) + 1);
61     Entry->Next = Bucket[Idx];
62     Bucket[Idx] = Entry;
63     __asan_poison_memory_region(Ptr, Capacity::get(Idx).getSize());
64   }
65 
66 public:
67   /// The size of an allocated array is represented by a Capacity instance.
68   ///
69   /// This class is much smaller than a size_t, and it provides methods to work
70   /// with the set of legal array capacities.
71   class Capacity {
72     uint8_t Index;
Capacity(uint8_t idx)73     explicit Capacity(uint8_t idx) : Index(idx) {}
74 
75   public:
Capacity()76     Capacity() : Index(0) {}
77 
78     /// Get the capacity of an array that can hold at least N elements.
get(size_t N)79     static Capacity get(size_t N) {
80       return Capacity(N ? Log2_64_Ceil(N) : 0);
81     }
82 
83     /// Get the number of elements in an array with this capacity.
getSize()84     size_t getSize() const { return size_t(1u) << Index; }
85 
86     /// Get the bucket number for this capacity.
getBucket()87     unsigned getBucket() const { return Index; }
88 
89     /// Get the next larger capacity. Large capacities grow exponentially, so
90     /// this function can be used to reallocate incrementally growing vectors
91     /// in amortized linear time.
getNext()92     Capacity getNext() const { return Capacity(Index + 1); }
93   };
94 
~ArrayRecycler()95   ~ArrayRecycler() {
96     // The client should always call clear() so recycled arrays can be returned
97     // to the allocator.
98     assert(Bucket.empty() && "Non-empty ArrayRecycler deleted!");
99   }
100 
101   /// Release all the tracked allocations to the allocator. The recycler must
102   /// be free of any tracked allocations before being deleted.
103   template<class AllocatorType>
clear(AllocatorType & Allocator)104   void clear(AllocatorType &Allocator) {
105     for (; !Bucket.empty(); Bucket.pop_back())
106       while (T *Ptr = pop(Bucket.size() - 1))
107         Allocator.Deallocate(Ptr);
108   }
109 
110   /// Special case for BumpPtrAllocator which has an empty Deallocate()
111   /// function.
112   ///
113   /// There is no need to traverse the free lists, pulling all the objects into
114   /// cache.
clear(BumpPtrAllocator &)115   void clear(BumpPtrAllocator&) {
116     Bucket.clear();
117   }
118 
119   /// Allocate an array of at least the requested capacity.
120   ///
121   /// Return an existing recycled array, or allocate one from Allocator if
122   /// none are available for recycling.
123   ///
124   template<class AllocatorType>
allocate(Capacity Cap,AllocatorType & Allocator)125   T *allocate(Capacity Cap, AllocatorType &Allocator) {
126     // Try to recycle an existing array.
127     if (T *Ptr = pop(Cap.getBucket()))
128       return Ptr;
129     // Nope, get more memory.
130     return static_cast<T*>(Allocator.Allocate(sizeof(T)*Cap.getSize(), Align));
131   }
132 
133   /// Deallocate an array with the specified Capacity.
134   ///
135   /// Cap must be the same capacity that was given to allocate().
136   ///
deallocate(Capacity Cap,T * Ptr)137   void deallocate(Capacity Cap, T *Ptr) {
138     push(Cap.getBucket(), Ptr);
139   }
140 };
141 
142 } // end llvm namespace
143 
144 #endif
145