source: doc/theses/mubeen_zulfiqar_MMath/allocator.tex @ 2e9b59b

ADTast-experimentalpthread-emulationqualifiedEnum
Last change on this file since 2e9b59b was 2e9b59b, checked in by m3zulfiq <m3zulfiq@…>, 22 months ago

added benchmark and evaluations chapter to thesis

  • Property mode set to 100644
File size: 62.1 KB
Line 
1\chapter{Allocator}
2
3This chapter presents a new stand-alone concurrent low-latency memory-allocator ($\approx$1,200 lines of code), called llheap (low-latency heap), for C/\CC programs using kernel threads (1:1 threading), and specialized versions of the allocator for the programming languages \uC and \CFA using user-level threads running over multiple kernel threads (M:N threading).
4The new allocator fulfills the GNU C Library allocator API~\cite{GNUallocAPI}.
5
6
7\section{llheap}
8
9The primary design objective for llheap is low-latency across all allocator calls independent of application access-patterns and/or number of threads, \ie very seldom does the allocator have a delay during an allocator call.
10(Large allocations requiring initialization, \eg zero fill, and/or copying are not covered by the low-latency objective.)
11A direct consequence of this objective is very simple or no storage coalescing;
12hence, llheap's design is willing to use more storage to lower latency.
13This objective is apropos because systems research and industrial applications are striving for low latency and computers have huge amounts of RAM memory.
14Finally, llheap's performance should be comparable with the current best allocators (see performance comparison in \VRef[Chapter]{c:Performance}).
15
16% The objective of llheap's new design was to fulfill following requirements:
17% \begin{itemize}
18% \item It should be concurrent and thread-safe for multi-threaded programs.
19% \item It should avoid global locks, on resources shared across all threads, as much as possible.
20% \item It's performance (FIX ME: cite performance benchmarks) should be comparable to the commonly used allocators (FIX ME: cite common allocators).
21% \item It should be a lightweight memory allocator.
22% \end{itemize}
23
24%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
25
26<<<<<<< HEAD
27\section{Design choices for uHeap}\label{sec:allocatorSec}
28uHeap's design was reviewed and changed to fulfill new requirements (FIX ME: cite allocator philosophy). For this purpose, following two designs of uHeapLmm were proposed:
29=======
30\section{Design Choices}
31>>>>>>> bb7c77dc425e289ed60aa638529b3e5c7c3e4961
32
33llheap's design was reviewed and changed multiple times throughout the thesis.
34Some of the rejected designs are discussed because they show the path to the final design (see discussion in \VRef{s:MultipleHeaps}).
35Note, a few simples tests for a design choice were compared with the current best allocators to determine the viability of a design.
36
37
38\subsection{Allocation Fastpath}
39\label{s:AllocationFastpath}
40
41These designs look at the allocation/free \newterm{fastpath}, \ie when an allocation can immediately return free storage or returned storage is not coalesced.
42\paragraph{T:1 model}
43\VRef[Figure]{f:T1SharedBuckets} shows one heap accessed by multiple kernel threads (KTs) using a bucket array, where smaller bucket sizes are N-shared across KTs.
44This design leverages the fact that 95\% of allocation requests are less than 1024 bytes and there are only 3--5 different request sizes.
45When KTs $\le$ N, the common bucket sizes are uncontented;
46when KTs $>$ N, the free buckets are contented and latency increases significantly.
47In all cases, a KT must acquire/release a lock, contented or uncontented, along the fast allocation path because a bucket is shared.
48Therefore, while threads are contending for a small number of buckets sizes, the buckets are distributed among them to reduce contention, which lowers latency;
49however, picking N is workload specific.
50
51\begin{figure}
52\centering
53\input{AllocDS1}
54\caption{T:1 with Shared Buckets}
55\label{f:T1SharedBuckets}
56\end{figure}
57
58Problems:
59\begin{itemize}
60\item
61Need to know when a KT is created/destroyed to assign/unassign a shared bucket-number from the memory allocator.
62\item
63When no thread is assigned a bucket number, its free storage is unavailable.
64\item
65All KTs contend for the global-pool lock for initial allocations, before free-lists get populated.
66\end{itemize}
67Tests showed having locks along the allocation fast-path produced a significant increase in allocation costs and any contention among KTs produces a significant spike in latency.
68
69\paragraph{T:H model}
70\VRef[Figure]{f:THSharedHeaps} shows a fixed number of heaps (N), each a local free pool, where the heaps are sharded across the KTs.
71A KT can point directly to its assigned heap or indirectly through the corresponding heap bucket.
72When KT $\le$ N, the heaps are uncontented;
73when KTs $>$ N, the heaps are contented.
74In all cases, a KT must acquire/release a lock, contented or uncontented along the fast allocation path because a heap is shared.
75By adjusting N upwards, this approach reduces contention but increases storage (time versus space);
76however, picking N is workload specific.
77
78\begin{figure}
79\centering
80\input{AllocDS2}
81\caption{T:H with Shared Heaps}
82\label{f:THSharedHeaps}
83\end{figure}
84
85Problems:
86\begin{itemize}
87\item
88Need to know when a KT is created/destroyed to assign/unassign a heap from the memory allocator.
89\item
90When no thread is assigned to a heap, its free storage is unavailable.
91\item
92Ownership issues arise (see \VRef{s:Ownership}).
93\item
94All KTs contend for the local/global-pool lock for initial allocations, before free-lists get populated.
95\end{itemize}
96Tests showed having locks along the allocation fast-path produced a significant increase in allocation costs and any contention among KTs produces a significant spike in latency.
97
98\paragraph{T:H model, H = number of CPUs}
99This design is the T:H model but H is set to the number of CPUs on the computer or the number restricted to an application, \eg via @taskset@.
100(See \VRef[Figure]{f:THSharedHeaps} but with a heap bucket per CPU.)
101Hence, each CPU logically has its own private heap and local pool.
102A memory operation is serviced from the heap associated with the CPU executing the operation.
103This approach removes fastpath locking and contention, regardless of the number of KTs mapped across the CPUs, because only one KT is running on each CPU at a time (modulo operations on the global pool and ownership).
104This approach is essentially an M:N approach where M is the number if KTs and N is the number of CPUs.
105
106Problems:
107\begin{itemize}
108\item
109Need to know when a CPU is added/removed from the @taskset@.
110\item
111Need a fast way to determine the CPU a KT is executing on to access the appropriate heap.
112\item
113Need to prevent preemption during a dynamic memory operation because of the \newterm{serially-reusable problem}.
114\begin{quote}
115A sequence of code that is guaranteed to run to completion before being invoked to accept another input is called serially-reusable code.~\cite{SeriallyReusable}
116\end{quote}
117If a KT is preempted during an allocation operation, the operating system can schedule another KT on the same CPU, which can begin an allocation operation before the previous operation associated with this CPU has completed, invalidating heap correctness.
118Note, the serially-reusable problem can occur in sequential programs with preemption, if the signal handler calls the preempted function, unless the function is serially reusable.
119Essentially, the serially-reusable problem is a race condition on an unprotected critical section, where the operating system is providing the second thread via the signal handler.
120
121Library @librseq@~\cite{librseq} was used to perform a fast determination of the CPU and to ensure all memory operations complete on one CPU using @librseq@'s restartable sequences, which restart the critical section after undoing its writes, if the critical section is preempted.
122\end{itemize}
123Tests showed that @librseq@ can determine the particular CPU quickly but setting up the restartable critical-section along the allocation fast-path produced a significant increase in allocation costs.
124Also, the number of undoable writes in @librseq@ is limited and restartable sequences cannot deal with user-level thread (UT) migration across KTs.
125For example, UT$_1$ is executing a memory operation by KT$_1$ on CPU$_1$ and a time-slice preemption occurs.
126The signal handler context switches UT$_1$ onto the user-level ready-queue and starts running UT$_2$ on KT$_1$, which immediately calls a memory operation.
127Since KT$_1$ is still executing on CPU$_1$, @librseq@ takes no action because it assumes KT$_1$ is still executing the same critical section.
128Then UT$_1$ is scheduled onto KT$_2$ by the user-level scheduler, and its memory operation continues in parallel with UT$_2$ using references into the heap associated with CPU$_1$, which corrupts CPU$_1$'s heap.
129If @librseq@ had an @rseq_abort@ which:
130\begin{enumerate}
131\item
132Marked the current restartable critical-section as cancelled so it restarts when attempting to commit.
133\item
134Do nothing if there is no current restartable critical section in progress.
135\end{enumerate}
136Then @rseq_abort@ could be called on the backside of a  user-level context-switching.
137A feature similar to this idea might exist for hardware transactional-memory.
138A significant effort was made to make this approach work but its complexity, lack of robustness, and performance costs resulted in its rejection.
139
140\paragraph{1:1 model}
141This design is the T:H model with T = H, where there is one thread-local heap for each KT.
142(See \VRef[Figure]{f:THSharedHeaps} but with a heap bucket per KT and no bucket or local-pool lock.)
143Hence, immediately after a KT starts, its heap is created and just before a KT terminates, its heap is (logically) deleted.
144Heaps are uncontended for a KTs memory operations to its heap (modulo operations on the global pool and ownership).
145
146Problems:
147\begin{itemize}
148\item
149Need to know when a KT is starts/terminates to create/delete its heap.
150
151\noindent
152It is possible to leverage constructors/destructors for thread-local objects to get a general handle on when a KT starts/terminates.
153\item
154There is a classic \newterm{memory-reclamation} problem for ownership because storage passed to another thread can be returned to a terminated heap.
155
156\noindent
157The classic solution only deletes a heap after all referents are returned, which is complex.
158The cheap alternative is for heaps to persist for program duration to handle outstanding referent frees.
159If old referents return storage to a terminated heap, it is handled in the same way as an active heap.
160To prevent heap blowup, terminated heaps can be reused by new KTs, where a reused heap may be populated with free storage from a prior KT (external fragmentation).
161In most cases, heap blowup is not a problem because programs have a small allocation set-size, so the free storage from a prior KT is apropos for a new KT.
162\item
163There can be significant external fragmentation as the number of KTs increases.
164
165\noindent
166In many concurrent applications, good performance is achieved with the number of KTs proportional to the number of CPUs.
167Since the number of CPUs is relatively small, >~1024, and a heap relatively small, $\approx$10K bytes (not including any associated freed storage), the worst-case external fragmentation is still small compared to the RAM available on large servers with many CPUs.
168\item
169There is the same serially-reusable problem with UTs migrating across KTs.
170\end{itemize}
171Tests showed this design produced the closest performance match with the best current allocators, and code inspection showed most of these allocators use different variations of this approach.
172
173
174\vspace{5pt}
175\noindent
176The conclusion from this design exercise is: any atomic fence, atomic instruction (lock free), or lock along the allocation fastpath produces significant slowdown.
177For the T:1 and T:H models, locking must exist along the allocation fastpath because the buckets or heaps maybe shared by multiple threads, even when KTs $\le$ N.
178For the T:H=CPU and 1:1 models, locking is eliminated along the allocation fastpath.
179However, T:H=CPU has poor operating-system support to determine the CPU id (heap id) and prevent the serially-reusable problem for KTs.
180More operating system support is required to make this model viable, but there is still the serially-reusable problem with user-level threading.
181Leaving the 1:1 model with no atomic actions along the fastpath and no special operating-system support required.
182The 1:1 model still has the serially-reusable problem with user-level threading, which is addressed in \VRef{s:UserlevelThreadingSupport}, and the greatest potential for heap blowup for certain allocation patterns.
183
184
185% \begin{itemize}
186% \item
187% A decentralized design is better to centralized design because their concurrency is better across all bucket-sizes as design 1 shards a few buckets of selected sizes while other designs shards all the buckets. Decentralized designs shard the whole heap which has all the buckets with the addition of sharding @sbrk@ area. So Design 1 was eliminated.
188% \item
189% Design 2 was eliminated because it has a possibility of contention in-case of KT > N while Design 3 and 4 have no contention in any scenario.
190% \item
191% Design 3 was eliminated because it was slower than Design 4 and it provided no way to achieve user-threading safety using librseq. We had to use CFA interruption handling to achieve user-threading safety which has some cost to it.
192% that  because of 4 was already slower than Design 3, adding cost of interruption handling on top of that would have made it even slower.
193% \end{itemize}
194% Of the four designs for a low-latency memory allocator, the 1:1 model was chosen for the following reasons:
195
196% \subsection{Advantages of distributed design}
197%
198% The distributed design of llheap is concurrent to work in multi-threaded applications.
199% Some key benefits of the distributed design of llheap are as follows:
200% \begin{itemize}
201% \item
202% The bump allocation is concurrent as memory taken from @sbrk@ is sharded across all heaps as bump allocation reserve. The call to @sbrk@ will be protected using locks but bump allocation (on memory taken from @sbrk@) will not be contended once the @sbrk@ call has returned.
203% \item
204% Low or almost no contention on heap resources.
205% \item
206% It is possible to use sharing and stealing techniques to share/find unused storage, when a free list is unused or empty.
207% \item
208% Distributed design avoids unnecessary locks on resources shared across all KTs.
209% \end{itemize}
210
211\subsection{Allocation Latency}
212
213A primary goal of llheap is low latency.
214Two forms of latency are internal and external.
215Internal latency is the time to perform an allocation, while external latency is time to obtain/return storage from/to the operating system.
216Ideally latency is $O(1)$ with a small constant.
217
218To obtain $O(1)$ internal latency means no searching on the allocation fastpath, largely prohibits coalescing, which leads to external fragmentation.
219The mitigating factor is that most programs have well behaved allocation patterns, where the majority of allocation operations can be $O(1)$, and heap blowup does not occur without coalescing (although the allocation footprint may be slightly larger).
220
221To obtain $O(1)$ external latency means obtaining one large storage area from the operating system and subdividing it across all program allocations, which requires a good guess at the program storage high-watermark and potential large external fragmentation.
222Excluding real-time operating-systems, operating-system operations are unbounded, and hence some external latency is unavoidable.
223The mitigating factor is that operating-system calls can often be reduced if a programmer has a sense of the storage high-watermark and the allocator is capable of using this information (see @malloc_expansion@ \VPageref{p:malloc_expansion}).
224Furthermore, while operating-system calls are unbounded, many are now reasonably fast, so their latency is tolerable and infrequent.
225
226
227%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
228
229\section{llheap Structure}
230
231\VRef[Figure]{f:llheapStructure} shows the design of llheap, which uses the following features:
232\begin{itemize}
233\item
2341:1 multiple-heap model to minimize the fastpath,
235\item
236can be built with or without heap ownership,
237\item
238headers per allocation versus containers,
239\item
240no coalescing to minimize latency,
241\item
242global heap memory (pool) obtained from the operating system using @mmap@ to create and reuse heaps needed by threads,
243\item
244local reserved memory (pool) per heap obtained from global pool,
245\item
246global reserved memory (pool) obtained from the operating system using @sbrk@ call,
247\item
248optional fast-lookup table for converting allocation requests into bucket sizes,
249\item
250optional statistic-counters table for accumulating counts of allocation operations.
251\end{itemize}
252
253\begin{figure}
254\centering
255<<<<<<< HEAD
256\includegraphics[width=0.65\textwidth]{figures/NewHeapStructure.eps}
257\caption{uHeap Structure}
258\label{fig:heapStructureFig}
259=======
260% \includegraphics[width=0.65\textwidth]{figures/NewHeapStructure.eps}
261\input{llheap}
262\caption{llheap Structure}
263\label{f:llheapStructure}
264>>>>>>> bb7c77dc425e289ed60aa638529b3e5c7c3e4961
265\end{figure}
266
267llheap starts by creating an array of $N$ global heaps from storage obtained using @mmap@, where $N$ is the number of computer cores, that persists for program duration.
268There is a global bump-pointer to the next free heap in the array.
269When this array is exhausted, another array is allocated.
270There is a global top pointer for a heap intrusive link to chain free heaps from terminated threads.
271When statistics are turned on, there is a global top pointer for a heap intrusive link to chain \emph{all} the heaps, which is traversed to accumulate statistics counters across heaps using @malloc_stats@.
272
273When a KT starts, a heap is allocated from the current array for exclusive use by the KT.
274When a KT terminates, its heap is chained onto the heap free-list for reuse by a new KT, which prevents unbounded growth of heaps.
275The free heaps is a stack so hot storage is reused first.
276Preserving all heaps created during the program lifetime, solves the storage lifetime problem, when ownership is used.
277This approach wastes storage if a large number of KTs are created/terminated at program start and then the program continues sequentially.
278llheap can be configured with object ownership, where an object is freed to the heap from which it is allocated, or object no-ownership, where an object is freed to the KT's current heap.
279
280Each heap uses segregated free-buckets that have free objects distributed across 91 different sizes from 16 to 4M.
281The number of buckets used is determined dynamically depending on the crossover point from @sbrk@ to @mmap@ allocation using @mallopt( M_MMAP_THRESHOLD )@, \ie small objects managed by the program and large objects managed by the operating system.
282Each free bucket of a specific size has the following two lists:
283\begin{itemize}
284\item
285A free stack used solely by the KT heap-owner, so push/pop operations do not require locking.
286The free objects are a stack so hot storage is reused first.
287\item
288For ownership, a shared away-stack for KTs to return storage allocated by other KTs, so push/pop operations require locking.
289When the free stack is empty, the entire ownership stack is removed and becomes the head of the corresponding free stack.
290\end{itemize}
291
292Algorithm~\ref{alg:heapObjectAlloc} shows the allocation outline for an object of size $S$.
293First, the allocation is divided into small (@sbrk@) or large (@mmap@).
294For large allocations, the storage is mapped directly from the operating system.
295For small allocations, $S$ is quantized into a bucket size.
296Quantizing is performed using a binary search over the ordered bucket array.
297An optional optimization is fast lookup $O(1)$ for sizes < 64K from a 64K array of type @char@, where each element has an index to the corresponding bucket.
298(Type @char@ restricts the number of bucket sizes to 256.)
299For $S$ > 64K, a binary search is used.
300Then, the allocation storage is obtained from the following locations (in order), with increasing latency.
301\begin{enumerate}[topsep=0pt,itemsep=0pt,parsep=0pt]
302\item
303bucket's free stack,
304\item
305bucket's away stack,
306\item
307heap's local pool
308\item
309global pool
310\item
311operating system (@sbrk@)
312\end{enumerate}
313
314\begin{figure}
315\vspace*{-10pt}
316\begin{algorithm}[H]
317\small
318\caption{Dynamic object allocation of size $S$}\label{alg:heapObjectAlloc}
319\begin{algorithmic}[1]
320\State $\textit{O} \gets \text{NULL}$
321\If {$S >= \textit{mmap-threshhold}$}
322        \State $\textit{O} \gets \text{allocate dynamic memory using system call mmap with size S}$
323\Else
324        \State $\textit{B} \gets \text{smallest free-bucket} \geq S$
325        \If {$\textit{B's free-list is empty}$}
326                \If {$\textit{B's away-list is empty}$}
327                        \If {$\textit{heap's allocation buffer} < S$}
328                                \State $\text{get allocation from global pool (which might call \lstinline{sbrk})}$
329                        \EndIf
330                        \State $\textit{O} \gets \text{bump allocate an object of size S from allocation buffer}$
331                \Else
332                        \State $\textit{merge B's away-list into free-list}$
333                        \State $\textit{O} \gets \text{pop an object from B's free-list}$
334                \EndIf
335        \Else
336                \State $\textit{O} \gets \text{pop an object from B's free-list}$
337        \EndIf
338        \State $\textit{O's owner} \gets \text{B}$
339\EndIf
340\State $\Return \textit{ O}$
341\end{algorithmic}
342\end{algorithm}
343
344<<<<<<< HEAD
345Algorithm~\ref{alg:heapObjectFreeOwn} shows how a free request is fulfilled if object ownership is turned on. Algorithm~\ref{alg:heapObjectFreeNoOwn} shows how the same free request is fulfilled without object ownership.
346
347\begin{algorithm}
348\caption{Dynamic object free at address A with object ownership}\label{alg:heapObjectFreeOwn}
349\begin{algorithmic}[1]
350\If {$\textit{A was mmap-ed}$}
351        \State $\text{return A's dynamic memory to system using system call munmap}$
352=======
353\vspace*{-15pt}
354\begin{algorithm}[H]
355\small
356\caption{Dynamic object free at address $A$ with object ownership}\label{alg:heapObjectFreeOwn}
357\begin{algorithmic}[1]
358\If {$\textit{A mapped allocation}$}
359        \State $\text{return A's dynamic memory to system using system call \lstinline{munmap}}$
360>>>>>>> bb7c77dc425e289ed60aa638529b3e5c7c3e4961
361\Else
362        \State $\text{B} \gets \textit{O's owner}$
363        \If {$\textit{B is thread-local heap's bucket}$}
364                \State $\text{push A to B's free-list}$
365        \Else
366                \State $\text{push A to B's away-list}$
367        \EndIf
368\EndIf
369\end{algorithmic}
370\end{algorithm}
371<<<<<<< HEAD
372
373\begin{algorithm}
374\caption{Dynamic object free at address A without object ownership}\label{alg:heapObjectFreeNoOwn}
375\begin{algorithmic}[1]
376\If {$\textit{A was mmap-ed}$}
377        \State $\text{return A's dynamic memory to system using system call munmap}$
378\Else
379        \State $\text{B} \gets \textit{O's owner}$
380        \If {$\textit{B is thread-local heap's bucket}$}
381                \State $\text{push A to B's free-list}$
382        \Else
383                \State $\text{C} \gets \textit{thread local heap's bucket with same size as B}$
384                \State $\text{push A to C's free-list}$
385        \EndIf
386\EndIf
387\end{algorithmic}
388\end{algorithm}
389
390=======
391>>>>>>> bb7c77dc425e289ed60aa638529b3e5c7c3e4961
392
393\vspace*{-15pt}
394\begin{algorithm}[H]
395\small
396\caption{Dynamic object free at address $A$ without object ownership}\label{alg:heapObjectFreeNoOwn}
397\begin{algorithmic}[1]
398\If {$\textit{A mapped allocation}$}
399        \State $\text{return A's dynamic memory to system using system call \lstinline{munmap}}$
400\Else
401        \State $\text{B} \gets \textit{O's owner}$
402        \If {$\textit{B is thread-local heap's bucket}$}
403                \State $\text{push A to B's free-list}$
404        \Else
405                \State $\text{C} \gets \textit{thread local heap's bucket with same size as B}$
406                \State $\text{push A to C's free-list}$
407        \EndIf
408\EndIf
409\end{algorithmic}
410\end{algorithm}
411\end{figure}
412
413Algorithm~\ref{alg:heapObjectFreeOwn} shows the de-allocation (free) outline for an object at address $A$ with ownership.
414First, the address is divided into small (@sbrk@) or large (@mmap@).
415For large allocations, the storage is unmapped back to the operating system.
416For small allocations, the bucket associated with the request size is retrieved.
417If the bucket is local to the thread, the allocation is pushed onto the thread's associated bucket.
418If the bucket is not local to the thread, the allocation is pushed onto the owning thread's associated away stack.
419
420Algorithm~\ref{alg:heapObjectFreeNoOwn} shows the de-allocation (free) outline for an object at address $A$ without ownership.
421The algorithm is the same as for ownership except if the bucket is not local to the thread.
422Then the corresponding bucket of the owner thread is computed for the deallocating thread, and the allocation is pushed onto the deallocating thread's bucket.
423
424Finally, the llheap design funnels \label{p:FunnelRoutine} all allocation/deallocation operations through routines @malloc@/@free@, which are the only routines to directly access and manage the internal data structures of the heap.
425Other allocation operations, \eg @calloc@, @memalign@, and @realloc@, are composed of calls to @malloc@ and possibly @free@, and may manipulate header information after storage is allocated.
426This design simplifies heap-management code during development and maintenance.
427
428
429\subsection{Alignment}
430
431All dynamic memory allocations must have a minimum storage alignment for the contained object(s).
432Often the minimum memory alignment, M, is the bus width (32 or 64-bit) or the largest register (double, long double) or largest atomic instruction (DCAS) or vector data (MMMX).
433In general, the minimum storage alignment is 8/16-byte boundary on 32/64-bit computers.
434For consistency, the object header is normally aligned at this same boundary.
435Larger alignments must be a power of 2, such page alignment (4/8K).
436Any alignment request, N, $\le$ the minimum alignment is handled as a normal allocation with minimal alignment.
437
438For alignments greater than the minimum, the obvious approach for aligning to address @A@ is: compute the next address that is a multiple of @N@ after the current end of the heap, @E@, plus room for the header before @A@ and the size of the allocation after @A@, moving the end of the heap to @E'@.
439\begin{center}
440\input{Alignment1}
441\end{center}
442The storage between @E@ and @H@ is chained onto the appropriate free list for future allocations.
443This approach is also valid within any sufficiently large free block, where @E@ is the start of the free block, and any unused storage before @H@ or after the allocated object becomes free storage.
444In this approach, the aligned address @A@ is the same as the allocated storage address @P@, \ie @P@ $=$ @A@ for all allocation routines, which simplifies deallocation.
445However, if there are a large number of aligned requests, this approach leads to memory fragmentation from the small free areas around the aligned object.
446As well, it does not work for large allocations, where many memory allocators switch from program @sbrk@ to operating-system @mmap@.
447The reason is that @mmap@ only starts on a page boundary, and it is difficult to reuse the storage before the alignment boundary for other requests.
448Finally, this approach is incompatible with allocator designs that funnel allocation requests through @malloc@ as it directly manipulates management information within the allocator to optimize the space/time of a request.
449
450Instead, llheap alignment is accomplished by making a \emph{pessimistically} allocation request for sufficient storage to ensure that \emph{both} the alignment and size request are satisfied, \eg:
451\begin{center}
452\input{Alignment2}
453\end{center}
454The amount of storage necessary is @alignment - M + size@, which ensures there is an address, @A@, after the storage returned from @malloc@, @P@, that is a multiple of @alignment@ followed by sufficient storage for the data object.
455The approach is pessimistic because if @P@ already has the correct alignment @N@, the initial allocation has already requested sufficient space to move to the next multiple of @N@.
456For this special case, there is @alignment - M@ bytes of unused storage after the data object, which subsequently can be used by @realloc@.
457
458Note, the address returned is @A@, which is subsequently returned to @free@.
459However, to correctly free the allocated object, the value @P@ must be computable, since that is the value generated by @malloc@ and returned within @memalign@.
460Hence, there must be a mechanism to detect when @P@ $\neq$ @A@ and how to compute @P@ from @A@.
461
462The llheap approach uses two headers:
463the \emph{original} header associated with a memory allocation from @malloc@, and a \emph{fake} header within this storage before the alignment boundary @A@, which is returned from @memalign@, e.g.:
464\begin{center}
465\input{Alignment2Impl}
466\end{center}
467Since @malloc@ has a minimum alignment of @M@, @P@ $\neq$ @A@ only holds for alignments of @M@ or greater.
468When @P@ $\neq$ @A@, the minimum distance between @P@ and @A@ is @M@ bytes, due to the pessimistic storage-allocation.
469Therefore, there is always room for an @M@-byte fake header before @A@.
470
471The fake header must supply an indicator to distinguish it from a normal header and the location of address @P@ generated by @malloc@.
472This information is encoded as an offset from A to P and the initialize alignment (discussed in \VRef{s:ReallocStickyProperties}).
473To distinguish a fake header from a normal header, the least-significant bit of the alignment is used because the offset participates in multiple calculations, while the alignment is just remembered data.
474\begin{center}
475\input{FakeHeader}
476\end{center}
477
478
479\subsection{\lstinline{realloc} and Sticky Properties}
480\label{s:ReallocStickyProperties}
481
482Allocation routine @realloc@ provides a memory-management pattern for shrinking/enlarging an existing allocation, while maintaining some or all of the object data, rather than performing the following steps manually.
483\begin{flushleft}
484\begin{tabular}{ll}
485\multicolumn{1}{c}{\textbf{realloc pattern}} & \multicolumn{1}{c}{\textbf{manually}} \\
486\begin{lstlisting}
487T * naddr = realloc( oaddr, newSize );
488
489
490
491\end{lstlisting}
492&
493\begin{lstlisting}
494T * naddr = (T *)malloc( newSize ); $\C[2.4in]{// new storage}$
495memcpy( naddr, addr, oldSize );  $\C{// copy old bytes}$
496free( addr );                           $\C{// free old storage}$
497addr = naddr;                           $\C{// change pointer}\CRT$
498\end{lstlisting}
499\end{tabular}
500\end{flushleft}
501The realloc pattern leverages available storage at the end of an allocation due to bucket sizes, possibly eliminating a new allocation and copying.
502This pattern is not used enough to reduce storage management costs.
503In fact, if @oaddr@ is @nullptr@, @realloc@ does a @malloc@, so even the initial @malloc@ can be a @realloc@ for consistency in the pattern.
504
505The hidden problem for this pattern is the effect of zero fill and alignment with respect to reallocation.
506Are these properties transient or persistent (``sticky'')?
507For example, when memory is initially allocated by @calloc@ or @memalign@ with zero fill or alignment properties, respectively, what happens when those allocations are given to @realloc@ to change size.
508That is, if @realloc@ logically extends storage into unused bucket space or allocates new storage to satisfy a size change, are initial allocation properties preserve?
509Currently, allocation properties are not preserved, so subsequent use of @realloc@ storage may cause inefficient execution or errors due to lack of zero fill or alignment.
510This silent problem is unintuitive to programmers and difficult to locate because it is transient.
511To prevent these problems, llheap preserves initial allocation properties for the lifetime of an allocation and the semantics of @realloc@ are augmented to preserve these properties, with additional query routines.
512This change makes the realloc pattern efficient and safe.
513
514
515\subsection{Header}
516
517To preserve allocation properties requires storing additional information with an allocation,
518The only available location is the header, where \VRef[Figure]{f:llheapNormalHeader} shows the llheap storage layout.
519The header has two data field sized appropriately for 32/64-bit alignment requirements.
520The first field is a union of three values:
521\begin{description}
522\item[bucket pointer]
523is for allocated storage and points back to the bucket associated with this storage requests (see \VRef[Figure]{f:llheapStructure} for the fields accessible in a bucket).
524\item[mapped size]
525is for mapped storage and is the storage size for use in unmapping.
526\item[next free block]
527is for free storage and is an intrusive pointer chaining same-size free blocks onto a bucket's free stack.
528\end{description}
529The second field remembers the request size versus the allocation (bucket) size, \eg request 42 bytes which is rounded up to 64 bytes.
530Since programmers think in request sizes rather than allocation sizes, the request size allows better generation of statistics or errors.
531
532\begin{figure}
533\centering
534\input{Header}
535\caption{llheap Normal Header}
536\label{f:llheapNormalHeader}
537\end{figure}
538
539The low-order 3-bits of the first field are \emph{unused} for any stored values, whereas the second field may use all of its bits.
540The 3 unused bits are used to represent mapped allocation, zero filled, and alignment, respectively.
541Note, the alignment bit is not used in the normal header and the zero-filled/mapped bits are not used in the fake header.
542This implementation allows a fast test if any of the lower 3-bits are on (@&@ and compare).
543If no bits are on, it implies a basic allocation, which is handled quickly;
544otherwise, the bits are analysed and appropriate actions are taken for the complex cases.
545Since most allocations are basic, this implementation results in a significant performance gain along the allocation and free fastpath.
546
547
548\section{Statistics and Debugging}
549
550llheap can be built to accumulate fast and largely contention-free allocation statistics to help understand allocation behaviour.
551Incrementing statistic counters must appear on the allocation fastpath.
552As noted, any atomic operation along the fastpath produces a significant increase in allocation costs.
553To make statistics performant enough for use on running systems, each heap has its own set of statistic counters, so heap operations do not require atomic operations.
554
555To locate all statistic counters, heaps are linked together in statistics mode, and this list is locked and traversed to sum all counters across heaps.
556Note, the list is locked to prevent errors traversing an active list;
557the statistics counters are not locked and can flicker during accumulation, which is not an issue with atomic read/write.
558\VRef[Figure]{f:StatiticsOutput} shows an example of statistics output, which covers all allocation operations and information about deallocating storage not owned by a thread.
559No other memory allocator studied provides as comprehensive statistical information.
560Finally, these statistics were invaluable during the development of this thesis for debugging and verifying correctness, and hence, should be equally valuable to application developers.
561
562\begin{figure}
563\begin{lstlisting}
564Heap statistics: (storage request / allocation)
565  malloc >0 calls 2,766; 0 calls 2,064; storage 12,715 / 13,367 bytes
566  aalloc >0 calls 0; 0 calls 0; storage 0 / 0 bytes
567  calloc >0 calls 6; 0 calls 0; storage 1,008 / 1,104 bytes
568  memalign >0 calls 0; 0 calls 0; storage 0 / 0 bytes
569  amemalign >0 calls 0; 0 calls 0; storage 0 / 0 bytes
570  cmemalign >0 calls 0; 0 calls 0; storage 0 / 0 bytes
571  resize >0 calls 0; 0 calls 0; storage 0 / 0 bytes
572  realloc >0 calls 0; 0 calls 0; storage 0 / 0 bytes
573  free !null calls 2,766; null calls 4,064; storage 12,715 / 13,367 bytes
574  away pulls 0; pushes 0; storage 0 / 0 bytes
575  sbrk calls 1; storage 10,485,760 bytes
576  mmap calls 10,000; storage 10,000 / 10,035 bytes
577  munmap calls 10,000; storage 10,000 / 10,035 bytes
578  threads started 4; exited 3
579  heaps new 4; reused 0
580\end{lstlisting}
581\caption{Statistics Output}
582\label{f:StatiticsOutput}
583\end{figure}
584
585llheap can also be built with debug checking, which inserts many asserts along all allocation paths.
586These assertions detect incorrect allocation usage, like double frees, unfreed storage, or memory corruptions because internal values (like header fields) are overwritten.
587These checks are best effort as opposed to complete allocation checking as in @valgrind@.
588Nevertheless, the checks detect many allocation problems.
589There is an unfortunate problem in detecting unfreed storage because some library routines assume their allocations have life-time duration, and hence, do not free their storage.
590For example, @printf@ allocates a 1024 buffer on first call and never deletes this buffer.
591To prevent a false positive for unfreed storage, it is possible to specify an amount of storage that is never freed (see @malloc_unfreed@ \VPageref{p:malloc_unfreed}), and it is subtracted from the total allocate/free difference.
592Determining the amount of never-freed storage is annoying, but once done, any warnings of unfreed storage are application related.
593
594Tests indicate only a 30\% performance increase when statistics \emph{and} debugging are enabled, and the latency cost for accumulating statistic is mitigated by limited calls, often only one at the end of the program.
595
596
597\section{User-level Threading Support}
598\label{s:UserlevelThreadingSupport}
599
600The serially-reusable problem (see \VRef{s:AllocationFastpath}) occurs for kernel threads in the ``T:H model, H = number of CPUs'' model and for user threads in the ``1:1'' model, where llheap uses the ``1:1'' model.
601The solution is to prevent interrupts that can result in CPU or KT change during operations that are logically critical sections.
602Locking these critical sections negates any attempt for a quick fastpath and results in high contention.
603For user-level threading, the serially-reusable problem appears with time slicing for preemptable scheduling, as the signal handler context switches to another user-level thread.
604Without time slicing, a user thread performing a long computation can prevent execution (starve) other threads.
605To prevent starvation for an allocation-active thread, \ie the time slice always triggers in an allocation critical-section for one thread, a thread-local \newterm{rollforward} flag is set in the signal handler when it aborts a time slice.
606The rollforward flag is tested at the end of each allocation funnel routine (see \VPageref{p:FunnelRoutine}), and if set, it is reset and a volunteer yield (context switch) is performed to allow other threads to execute.
607
608llheap uses two techniques to detect when execution is in a allocation operation or routine called from allocation operation, to abort any time slice during this period.
609On the slowpath when executing expensive operations, like @sbrk@ or @mmap@, interrupts are disabled/enabled by setting thread-local flags so the signal handler aborts immediately.
610On the fastpath, disabling/enabling interrupts is too expensive as accessing thread-local storage can be expensive and not thread-safe.
611For example, the ARM processor stores the thread-local pointer in a coprocessor register that cannot perform atomic base-displacement addressing.
612Hence, there is a window between loading the thread-local pointer from the coprocessor register into a normal register and adding the displacement when a time slice can move a thread.
613
614The fast technique defines a special code section and places all non-interruptible routines in this section.
615The linker places all code in this section into a contiguous block of memory, but the order of routines within the block is unspecified.
616Then, the signal handler compares the program counter at the point of interrupt with the the start and end address of the non-interruptible section, and aborts if executing within this section and sets the rollforward flag.
617This technique is fragile because any calls in the non-interruptible code outside of the non-interruptible section (like @sbrk@) must be bracketed with disable/enable interrupts and these calls must be along the slowpath.
618Hence, for correctness, this approach requires inspection of generated assembler code for routines placed in the non-interruptible section.
619This issue is mitigated by the llheap funnel design so only funnel routines and a few statistics routines are placed in the non-interruptible section and their assembler code examined.
620These techniques are used in both the \uC and \CFA versions of llheap, where both of these systems have user-level threading.
621
622
623\section{Bootstrapping}
624
625There are problems bootstrapping a memory allocator.
626\begin{enumerate}
627\item
628Programs can be statically or dynamically linked.
629\item
630The order the linker schedules startup code is poorly supported.
631\item
632Knowing a KT's start and end independently from the KT code is difficult.
633\end{enumerate}
634
635For static linking, the allocator is loaded with the program.
636Hence, allocation calls immediately invoke the allocator operation defined by the loaded allocation library and there is only one memory allocator used in the program.
637This approach allows allocator substitution by placing an allocation library before any other in the linked/load path.
638
639Allocator substitution is similar for dynamic linking, but the problem is that the dynamic loader starts first and needs to perform dynamic allocations \emph{before} the substitution allocator is loaded.
640As a result, the dynamic loader uses a default allocator until the substitution allocator is loaded, after which all allocation operations are handled by the substitution allocator, including from the dynamic loader.
641Hence, some part of the @sbrk@ area may be used by the default allocator and statistics about allocation operations cannot be correct.
642Furthermore, dynamic linking goes through trampolines, so there is an additional cost along the allocator fastpath for all allocation operations.
643Testing showed up to a 5\% performance increase for dynamic linking over static linking, even when using @tls_model("initial-exec")@ so the dynamic loader can obtain tighter binding.
644
645All allocator libraries need to perform startup code to initialize data structures, such as the heap array for llheap.
646The problem is getting initialized done before the first allocator call.
647However, there does not seem to be mechanism to tell either the static or dynamic loader to first perform initialization code before any calls to a loaded library.
648As a result, calls to allocation routines occur without initialization.
649To deal with this problem, it is necessary to put a conditional initialization check along the allocation fastpath to trigger initialization (singleton pattern).
650
651Two other important execution points are program startup and termination, which include prologue or epilogue code to bootstrap a program, which programmers are unaware of.
652For example, dynamic-memory allocations before/after the application starts should not be considered in statistics because the application does not make these calls.
653llheap establishes these two points using routines:
654\begin{lstlisting}
655__attribute__(( constructor( 100 ) )) static void startup( void ) {
656        // clear statistic counters
657        // reset allocUnfreed counter
658}
659__attribute__(( destructor( 100 ) )) static void shutdown( void ) {
660        // sum allocUnfreed for all heaps
661        // subtract global unfreed storage
662        // if allocUnfreed > 0 then print warning message
663}
664\end{lstlisting}
665which use global constructor/destructor priority 100, where the linker calls these routines at program prologue/epilogue in increasing/decreasing order of priority.
666Application programs may only use global constructor/destructor priorities greater than 100.
667Hence, @startup@ is called after the program prologue but before the application starts, and @shutdown@ is called after the program terminates but before the program epilogue.
668By resetting counters in @startup@, prologue allocations are ignored, and checking unfreed storage in @shutdown@ checks only application memory management, ignoring the program epilogue.
669
670While @startup@/@shutdown@ apply to the program KT, a concurrent program creates additional KTs that do not trigger these routines.
671However, it is essential for the allocator to know when each KT is started/terminated.
672One approach is to create a thread-local object with a construct/destructor, which is triggered after a new KT starts and before it terminates, respectively.
673\begin{lstlisting}
674struct ThreadManager {
675        volatile bool pgm_thread;
676        ThreadManager() {} // unusable
677        ~ThreadManager() { if ( pgm_thread ) heapManagerDtor(); }
678};
679static thread_local ThreadManager threadManager;
680\end{lstlisting}
681Unfortunately, thread-local variables are created lazily, \ie on the first dereference of @threadManager@, which then triggers its constructor.
682Therefore, the constructor is useless for knowing when a KT starts because the KT must reference it, and the allocator does not control the application KT.
683Fortunately, the singleton pattern needed for initializing the program KT also triggers KT allocator initialization, which can then reference @pgm_thread@ to call @threadManager@'s constructor, otherwise its destructor is not called.
684Now when a KT terminates, @~ThreadManager@ is called to chained it onto the global-heap free-stack, where @pgm_thread@ is set to true only for the program KT.
685The conditional destructor call prevents closing down the program heap, which must remain available because epilogue code may free more storage.
686
687Finally, there is a recursive problem when the singleton pattern dereferences @pgm_thread@ to initialize the thread-local object, because its initialization calls @atExit@, which immediately calls @malloc@ to obtain storage.
688This recursion is handled with another thread-local flag to prevent double initialization.
689A similar problem exists when the KT terminates and calls member @~ThreadManager@, because immediately afterwards, the terminating KT calls @free@ to deallocate the storage obtained from the @atExit@.
690In the meantime, the terminated heap has been put on the global-heap free-stack, and may be active by a new KT, so the @atExit@ free is handled as a free to another heap and put onto the away list using locking.
691
692For user threading systems, the KTs are controlled by the runtime, and hence, start/end pointers are known and interact directly with the llheap allocator for \uC and \CFA, which eliminates or simplifies several of these problems.
693The following API was created to provide interaction between the language runtime and the allocator.
694\begin{lstlisting}
695void startTask();                       $\C{// KT starts}$
696void finishTask();                      $\C{// KT ends}$
697void startup();                         $\C{// when application code starts}$
698void shutdown();                        $\C{// when application code ends}$
699bool traceHeap();                       $\C{// enable allocation/free printing for debugging}$
700bool traceHeapOn();                     $\C{// start printing allocation/free calls}$
701bool traceHeapOff();                    $\C{// stop printing allocation/free calls}$
702\end{lstlisting}
703This kind of API is necessary to allow concurrent runtime systems to interact with difference memory allocators in a consistent way.
704
705%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
706
707\section{Added Features and Methods}
708
709The C dynamic-allocation API (see \VRef[Figure]{f:CDynamicAllocationAPI}) is neither orthogonal nor complete.
710For example,
711\begin{itemize}
712\item
713It is possible to zero fill or align an allocation but not both.
714\item
715It is \emph{only} possible to zero fill an array allocation.
716\item
717It is not possible to resize a memory allocation without data copying.
718\item
719@realloc@ does not preserve initial allocation properties.
720\end{itemize}
721As a result, programmers must provide these options, which is error prone, resulting in blaming the entire programming language for a poor dynamic-allocation API.
722Furthermore, newer programming languages have better type systems that can provide safer and more powerful APIs for memory allocation.
723
724\begin{figure}
725\begin{lstlisting}
726void * malloc( size_t size );
727void * calloc( size_t nmemb, size_t size );
728void * realloc( void * ptr, size_t size );
729void * reallocarray( void * ptr, size_t nmemb, size_t size );
730void free( void * ptr );
731void * memalign( size_t alignment, size_t size );
732void * aligned_alloc( size_t alignment, size_t size );
733int posix_memalign( void ** memptr, size_t alignment, size_t size );
734void * valloc( size_t size );
735void * pvalloc( size_t size );
736
737struct mallinfo mallinfo( void );
738int mallopt( int param, int val );
739int malloc_trim( size_t pad );
740size_t malloc_usable_size( void * ptr );
741void malloc_stats( void );
742int malloc_info( int options, FILE * fp );
743\end{lstlisting}
744\caption{C Dynamic-Allocation API}
745\label{f:CDynamicAllocationAPI}
746\end{figure}
747
748The following presents design and API changes for C, \CC (\uC), and \CFA, all of which are implemented in llheap.
749
750
751\subsection{Out of Memory}
752
753Most allocators use @nullptr@ to indicate an allocation failure, specifically out of memory;
754hence the need to return an alternate value for a zero-sized allocation.
755A different approach allowed by the C API is to abort a program when out of memory and return @nullptr@ for a zero-sized allocation.
756In theory, notifying the programmer of memory failure allows recovery;
757in practice, it is almost impossible to gracefully recover when out of memory.
758Hence, the cheaper approach of returning @nullptr@ for a zero-sized allocation is chosen because no pseudo allocation is necessary.
759
760
761\subsection{C Interface}
762
763For C, it is possible to increase functionality and orthogonality of the dynamic-memory API to make allocation better for programmers.
764
765For existing C allocation routines:
766\begin{itemize}
767\item
768@calloc@ sets the sticky zero-fill property.
769\item
770@memalign@, @aligned_alloc@, @posix_memalign@, @valloc@ and @pvalloc@ set the sticky alignment property.
771\item
772@realloc@ and @reallocarray@ preserve sticky properties.
773\end{itemize}
774
775The C dynamic-memory API is extended with the following routines:
776
777\paragraph{\lstinline{void * aalloc( size_t dim, size_t elemSize )}}
778extends @calloc@ for allocating a dynamic array of objects without calculating the total size of array explicitly but \emph{without} zero-filling the memory.
779@aalloc@ is significantly faster than @calloc@, which is the only alternative.
780
781\noindent\textbf{Usage}
782@aalloc@ takes two parameters.
783\begin{itemize}
784\item
785@dim@: number of array objects
786\item
787@elemSize@: size of array object
788\end{itemize}
789It returns the address of the dynamic array or @NULL@ if either @dim@ or @elemSize@ are zero.
790
791\paragraph{\lstinline{void * resize( void * oaddr, size_t size )}}
792extends @realloc@ for resizing an existing allocation \emph{without} copying previous data into the new allocation or preserving sticky properties.
793@resize@ is significantly faster than @realloc@, which is the only alternative.
794
795\noindent\textbf{Usage}
796@resize@ takes two parameters.
797\begin{itemize}
798\item
799@oaddr@: address to be resized
800\item
801@size@: new allocation size (smaller or larger than previous)
802\end{itemize}
803It returns the address of the old or new storage with the specified new size or @NULL@ if @size@ is zero.
804
805\paragraph{\lstinline{void * amemalign( size_t alignment, size_t dim, size_t elemSize )}}
806extends @aalloc@ and @memalign@ for allocating an aligned dynamic array of objects.
807Sets sticky alignment property.
808
809\noindent\textbf{Usage}
810@amemalign@ takes three parameters.
811\begin{itemize}
812\item
813@alignment@: alignment requirement
814\item
815@dim@: number of array objects
816\item
817@elemSize@: size of array object
818\end{itemize}
819It returns the address of the aligned dynamic-array or @NULL@ if either @dim@ or @elemSize@ are zero.
820
821\paragraph{\lstinline{void * cmemalign( size_t alignment, size_t dim, size_t elemSize )}}
822extends @amemalign@ with zero fill and has the same usage as @amemalign@.
823Sets sticky zero-fill and alignment property.
824It returns the address of the aligned, zero-filled dynamic-array or @NULL@ if either @dim@ or @elemSize@ are zero.
825
826\paragraph{\lstinline{size_t malloc_alignment( void * addr )}}
827returns the alignment of the dynamic object for use in aligning similar allocations.
828
829\noindent\textbf{Usage}
830@malloc_alignment@ takes one parameter.
831\begin{itemize}
832\item
833@addr@: address of an allocated object.
834\end{itemize}
835It returns the alignment of the given object, where objects not allocated with alignment return the minimal allocation alignment.
836
837\paragraph{\lstinline{bool malloc_zero_fill( void * addr )}}
838returns true if the object has the zero-fill sticky property for use in zero filling similar allocations.
839
840\noindent\textbf{Usage}
841@malloc_zero_fill@ takes one parameters.
842
843\begin{itemize}
844\item
845@addr@: address of an allocated object.
846\end{itemize}
847It returns true if the zero-fill sticky property is set and false otherwise.
848
849\paragraph{\lstinline{size_t malloc_size( void * addr )}}
850returns the request size of the dynamic object (updated when an object is resized) for use in similar allocations.
851See also @malloc_usable_size@.
852
853\noindent\textbf{Usage}
854@malloc_size@ takes one parameters.
855\begin{itemize}
856\item
857@addr@: address of an allocated object.
858\end{itemize}
859It returns the request size or zero if @addr@ is @NULL@.
860
861\paragraph{\lstinline{int malloc_stats_fd( int fd )}}
862changes the file descriptor where @malloc_stats@ writes statistics (default @stdout@).
863
864\noindent\textbf{Usage}
865@malloc_stats_fd@ takes one parameters.
866\begin{itemize}
867\item
868@fd@: files description.
869\end{itemize}
870It returns the previous file descriptor.
871
872\paragraph{\lstinline{size_t malloc_expansion()}}
873\label{p:malloc_expansion}
874set the amount (bytes) to extend the heap when there is insufficient free storage to service an allocation request.
875It returns the heap extension size used throughout a program, \ie called once at heap initialization.
876
877\paragraph{\lstinline{size_t malloc_mmap_start()}}
878set the crossover between allocations occurring in the @sbrk@ area or separately mapped.
879It returns the crossover point used throughout a program, \ie called once at heap initialization.
880
881\paragraph{\lstinline{size_t malloc_unfreed()}}
882\label{p:malloc_unfreed}
883amount subtracted to adjust for unfreed program storage (debug only).
884It returns the new subtraction amount and called by @malloc_stats@.
885
886
887\subsection{\CC Interface}
888
889The following extensions take advantage of overload polymorphism in the \CC type-system.
890
891\paragraph{\lstinline{void * resize( void * oaddr, size_t nalign, size_t size )}}
892extends @resize@ with an alignment re\-quirement.
893
894\noindent\textbf{Usage}
895takes three parameters.
896\begin{itemize}
897\item
898@oaddr@: address to be resized
899\item
900@nalign@: alignment requirement
901\item
902@size@: new allocation size (smaller or larger than previous)
903\end{itemize}
904It returns the address of the old or new storage with the specified new size and alignment, or @NULL@ if @size@ is zero.
905
906\paragraph{\lstinline{void * realloc( void * oaddr, size_t nalign, size_t size )}}
907extends @realloc@ with an alignment re\-quirement and has the same usage as aligned @resize@.
908
909
910\subsection{\CFA Interface}
911
912The following extensions take advantage of overload polymorphism in the \CFA type-system.
913The key safety advantage of the \CFA type system is using the return type to select overloads;
914hence, a polymorphic routine knows the returned type and its size.
915This capability is used to remove the object size parameter and correctly cast the return storage to match the result type.
916For example, the following is the \CFA wrapper for C @malloc@:
917\begin{cfa}
918forall( T & | sized(T) ) {
919        T * malloc( void ) {
920                if ( _Alignof(T) <= libAlign() ) return @(T *)@malloc( @sizeof(T)@ ); // C allocation
921                else return @(T *)@memalign( @_Alignof(T)@, @sizeof(T)@ ); // C allocation
922        } // malloc
923\end{cfa}
924and is used as follows:
925\begin{lstlisting}
926int * i = malloc();
927double * d = malloc();
928struct Spinlock { ... } __attribute__(( aligned(128) ));
929Spinlock * sl = malloc();
930\end{lstlisting}
931where each @malloc@ call provides the return type as @T@, which is used with @sizeof@, @_Alignof@, and casting the storage to the correct type.
932This interface removes many of the common allocation errors in C programs.
933\VRef[Figure]{f:CFADynamicAllocationAPI} show the \CFA wrappers for the equivalent C/\CC allocation routines with same semantic behaviour.
934
935\begin{figure}
936\begin{lstlisting}
937T * malloc( void );
938T * aalloc( size_t dim );
939T * calloc( size_t dim );
940T * resize( T * ptr, size_t size );
941T * realloc( T * ptr, size_t size );
942T * memalign( size_t align );
943T * amemalign( size_t align, size_t dim );
944T * cmemalign( size_t align, size_t dim  );
945T * aligned_alloc( size_t align );
946int posix_memalign( T ** ptr, size_t align );
947T * valloc( void );
948T * pvalloc( void );
949\end{lstlisting}
950\caption{\CFA C-Style Dynamic-Allocation API}
951\label{f:CFADynamicAllocationAPI}
952\end{figure}
953
954In addition to the \CFA C-style allocator interface, a new allocator interface is provided to further increase orthogonality and usability of dynamic-memory allocation.
955This interface helps programmers in three ways.
956\begin{itemize}
957\item
958naming: \CFA regular and @ttype@ polymorphism is used to encapsulate a wide range of allocation functionality into a single routine name, so programmers do not have to remember multiple routine names for different kinds of dynamic allocations.
959\item
960named arguments: individual allocation properties are specified using postfix function call, so programmers do have to remember parameter positions in allocation calls.
961\item
962object size: like the \CFA C-style interface, programmers do not have to specify object size or cast allocation results.
963\end{itemize}
964Note, postfix function call is an alternative call syntax, using backtick @`@, where the argument appears before the function name, \eg
965\begin{cfa}
966duration ?@`@h( int h );                // ? denote the position of the function operand
967duration ?@`@m( int m );
968duration ?@`@s( int s );
969duration dur = 3@`@h + 42@`@m + 17@`@s;
970\end{cfa}
971@ttype@ polymorphism is similar to \CC variadic templates.
972
973\paragraph{\lstinline{T * alloc( ... )} or \lstinline{T * alloc( size_t dim, ... )}}
974is overloaded with a variable number of specific allocation routines, or an integer dimension parameter followed by a variable number specific allocation routines.
975A call without parameters returns a dynamically allocated object of type @T@ (@malloc@).
976A call with only the dimension (dim) parameter returns a dynamically allocated array of objects of type @T@ (@aalloc@).
977The variable number of arguments consist of allocation properties, which can be combined to produce different kinds of allocations.
978The only restriction is for properties @realloc@ and @resize@, which cannot be combined.
979
980The allocation property functions are:
981\subparagraph{\lstinline{T_align ?`align( size_t alignment )}}
982to align the allocation.
983The alignment parameter must be $\ge$ the default alignment (@libAlign()@ in \CFA) and a power of two, \eg:
984\begin{cfa}
985int * i0 = alloc( @4096`align@ );  sout | i0 | nl;
986int * i1 = alloc( 3, @4096`align@ );  sout | i1; for (i; 3 ) sout | &i1[i]; sout | nl;
987
9880x555555572000
9890x555555574000 0x555555574000 0x555555574004 0x555555574008
990\end{cfa}
991returns a dynamic object and object array aligned on a 4096-byte boundary.
992
993\subparagraph{\lstinline{S_fill(T) ?`fill ( /* various types */ )}}
994to initialize storage.
995There are three ways to fill storage:
996\begin{enumerate}
997\item
998A char fills each byte of each object.
999\item
1000An object of the returned type fills each object.
1001\item
1002An object array pointer fills some or all of the corresponding object array.
1003\end{enumerate}
1004For example:
1005\begin{cfa}[numbers=left]
1006int * i0 = alloc( @0n`fill@ );  sout | *i0 | nl;  // disambiguate 0
1007int * i1 = alloc( @5`fill@ );  sout | *i1 | nl;
1008int * i2 = alloc( @'\xfe'`fill@ ); sout | hex( *i2 ) | nl;
1009int * i3 = alloc( 5, @5`fill@ );  for ( i; 5 ) sout | i3[i]; sout | nl;
1010int * i4 = alloc( 5, @0xdeadbeefN`fill@ );  for ( i; 5 ) sout | hex( i4[i] ); sout | nl;
1011int * i5 = alloc( 5, @i3`fill@ );  for ( i; 5 ) sout | i5[i]; sout | nl;
1012int * i6 = alloc( 5, @[i3, 3]`fill@ );  for ( i; 5 ) sout | i6[i]; sout | nl;
1013\end{cfa}
1014\begin{lstlisting}[numbers=left]
10150
10165
10170xfefefefe
10185 5 5 5 5
10190xdeadbeef 0xdeadbeef 0xdeadbeef 0xdeadbeef 0xdeadbeef
10205 5 5 5 5
10215 5 5 -555819298 -555819298  // two undefined values
1022\end{lstlisting}
1023Examples 1 to 3, fill an object with a value or characters.
1024Examples 4 to 7, fill an array of objects with values, another array, or part of an array.
1025
1026\subparagraph{\lstinline{S_resize(T) ?`resize( void * oaddr )}}
1027used to resize, realign, and fill, where the old object data is not copied to the new object.
1028The old object type may be different from the new object type, since the values are not used.
1029For example:
1030\begin{cfa}[numbers=left]
1031int * i = alloc( @5`fill@ );  sout | i | *i;
1032i = alloc( @i`resize@, @256`align@, @7`fill@ );  sout | i | *i;
1033double * d = alloc( @i`resize@, @4096`align@, @13.5`fill@ );  sout | d | *d;
1034\end{cfa}
1035\begin{lstlisting}[numbers=left]
10360x55555556d5c0 5
10370x555555570000 7
10380x555555571000 13.5
1039\end{lstlisting}
1040Examples 2 to 3 change the alignment, fill, and size for the initial storage of @i@.
1041
1042\begin{cfa}[numbers=left]
1043int * ia = alloc( 5, @5`fill@ );  for ( i; 5 ) sout | ia[i]; sout | nl;
1044ia = alloc( 10, @ia`resize@, @7`fill@ ); for ( i; 10 ) sout | ia[i]; sout | nl;
1045sout | ia; ia = alloc( 5, @ia`resize@, @512`align@, @13`fill@ ); sout | ia; for ( i; 5 ) sout | ia[i]; sout | nl;;
1046ia = alloc( 3, @ia`resize@, @4096`align@, @2`fill@ );  sout | ia; for ( i; 3 ) sout | &ia[i] | ia[i]; sout | nl;
1047\end{cfa}
1048\begin{lstlisting}[numbers=left]
10495 5 5 5 5
10507 7 7 7 7 7 7 7 7 7
10510x55555556d560 0x555555571a00 13 13 13 13 13
10520x555555572000 0x555555572000 2 0x555555572004 2 0x555555572008 2
1053\end{lstlisting}
1054Examples 2 to 4 change the array size, alignment and fill for the initial storage of @ia@.
1055
1056\subparagraph{\lstinline{S_realloc(T) ?`realloc( T * a ))}}
1057used to resize, realign, and fill, where the old object data is copied to the new object.
1058The old object type must be the same as the new object type, since the values used.
1059Note, for @fill@, only the extra space after copying the data from the old object is filled with the given parameter.
1060For example:
1061\begin{cfa}[numbers=left]
1062int * i = alloc( @5`fill@ );  sout | i | *i;
1063i = alloc( @i`realloc@, @256`align@ );  sout | i | *i;
1064i = alloc( @i`realloc@, @4096`align@, @13`fill@ );  sout | i | *i;
1065\end{cfa}
1066\begin{lstlisting}[numbers=left]
10670x55555556d5c0 5
10680x555555570000 5
10690x555555571000 5
1070\end{lstlisting}
1071Examples 2 to 3 change the alignment for the initial storage of @i@.
1072The @13`fill@ for example 3 does nothing because no extra space is added.
1073
1074\begin{cfa}[numbers=left]
1075int * ia = alloc( 5, @5`fill@ );  for ( i; 5 ) sout | ia[i]; sout | nl;
1076ia = alloc( 10, @ia`realloc@, @7`fill@ ); for ( i; 10 ) sout | ia[i]; sout | nl;
1077sout | ia; ia = alloc( 1, @ia`realloc@, @512`align@, @13`fill@ ); sout | ia; for ( i; 1 ) sout | ia[i]; sout | nl;;
1078ia = alloc( 3, @ia`realloc@, @4096`align@, @2`fill@ );  sout | ia; for ( i; 3 ) sout | &ia[i] | ia[i]; sout | nl;
1079\end{cfa}
1080\begin{lstlisting}[numbers=left]
10815 5 5 5 5
10825 5 5 5 5 7 7 7 7 7
10830x55555556c560 0x555555570a00 5
10840x555555571000 0x555555571000 5 0x555555571004 2 0x555555571008 2
1085\end{lstlisting}
1086Examples 2 to 4 change the array size, alignment and fill for the initial storage of @ia@.
1087The @13`fill@ for example 3 does nothing because no extra space is added.
1088
1089These \CFA allocation features are used extensively in the development of the \CFA runtime.
Note: See TracBrowser for help on using the repository browser.