source: doc/theses/mubeen_zulfiqar_MMath/allocator.tex @ 23f1065

ADTast-experimentalpthread-emulationqualifiedEnum
Last change on this file since 23f1065 was 23f1065, checked in by Peter A. Buhr <pabuhr@…>, 23 months ago

small wording changes to intro and background chapters, continue proofreading allocator chapter

  • Property mode set to 100644
File size: 68.3 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\section{Design Choices}
27
28llheap's design was reviewed and changed multiple times throughout the thesis.
29Some of the rejected designs are discussed because they show the path to the final design (see discussion in \VRef{s:MultipleHeaps}).
30Note, a few simples tests for a design choice were compared with the current best allocators to determine the viability of a design.
31
32
33\subsection{Allocation Fastpath}
34\label{s:AllocationFastpath}
35
36These designs look at the allocation/free \newterm{fastpath}, \ie when an allocation can immediately return free storage or returned storage is not coalesced.
37\paragraph{T:1 model}
38\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.
39This design leverages the fact that 95\% of allocation requests are less than 1024 bytes and there are only 3--5 different request sizes.
40When KTs $\le$ N, the common bucket sizes are uncontented;
41when KTs $>$ N, the free buckets are contented and latency increases significantly.
42In all cases, a KT must acquire/release a lock, contented or uncontented, along the fast allocation path because a bucket is shared.
43Therefore, while threads are contending for a small number of buckets sizes, the buckets are distributed among them to reduce contention, which lowers latency;
44however, picking N is workload specific.
45
46\begin{figure}
47\centering
48\input{AllocDS1}
49\caption{T:1 with Shared Buckets}
50\label{f:T1SharedBuckets}
51\end{figure}
52
53Problems:
54\begin{itemize}
55\item
56Need to know when a KT is created/destroyed to assign/unassign a shared bucket-number from the memory allocator.
57\item
58When no thread is assigned a bucket number, its free storage is unavailable.
59\item
60All KTs contend for the global-pool lock for initial allocations, before free-lists get populated.
61\end{itemize}
62Tests 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.
63
64\paragraph{T:H model}
65\VRef[Figure]{f:THSharedHeaps} shows a fixed number of heaps (N), each a local free pool, where the heaps are sharded across the KTs.
66A KT can point directly to its assigned heap or indirectly through the corresponding heap bucket.
67When KT $\le$ N, the heaps are uncontented;
68when KTs $>$ N, the heaps are contented.
69In all cases, a KT must acquire/release a lock, contented or uncontented along the fast allocation path because a heap is shared.
70By adjusting N upwards, this approach reduces contention but increases storage (time versus space);
71however, picking N is workload specific.
72
73\begin{figure}
74\centering
75\input{AllocDS2}
76\caption{T:H with Shared Heaps}
77\label{f:THSharedHeaps}
78\end{figure}
79
80Problems:
81\begin{itemize}
82\item
83Need to know when a KT is created/destroyed to assign/unassign a heap from the memory allocator.
84\item
85When no thread is assigned to a heap, its free storage is unavailable.
86\item
87Ownership issues arise (see \VRef{s:Ownership}).
88\item
89All KTs contend for the local/global-pool lock for initial allocations, before free-lists get populated.
90\end{itemize}
91Tests 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.
92
93\paragraph{T:H model, H = number of CPUs}
94This 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@.
95(See \VRef[Figure]{f:THSharedHeaps} but with a heap bucket per CPU.)
96Hence, each CPU logically has its own private heap and local pool.
97A memory operation is serviced from the heap associated with the CPU executing the operation.
98This 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).
99This approach is essentially an M:N approach where M is the number if KTs and N is the number of CPUs.
100
101Problems:
102\begin{itemize}
103\item
104Need to know when a CPU is added/removed from the @taskset@.
105\item
106Need a fast way to determine the CPU a KT is executing on to access the appropriate heap.
107\item
108Need to prevent preemption during a dynamic memory operation because of the \newterm{serially-reusable problem}.
109\begin{quote}
110A sequence of code that is guaranteed to run to completion before being invoked to accept another input is called serially-reusable code.~\cite{SeriallyReusable}
111\end{quote}
112If 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.
113Note, 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.
114Essentially, 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.
115
116Library @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.
117\end{itemize}
118Tests 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.
119Also, the number of undoable writes in @librseq@ is limited and restartable sequences cannot deal with user-level thread (UT) migration across KTs.
120For example, UT$_1$ is executing a memory operation by KT$_1$ on CPU$_1$ and a time-slice preemption occurs.
121The 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.
122Since KT$_1$ is still executing on CPU$_1$, @librseq@ takes no action because it assumes KT$_1$ is still executing the same critical section.
123Then 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.
124If @librseq@ had an @rseq_abort@ which:
125\begin{enumerate}
126\item
127Marked the current restartable critical-section as cancelled so it restarts when attempting to commit.
128\item
129Do nothing if there is no current restartable critical section in progress.
130\end{enumerate}
131Then @rseq_abort@ could be called on the backside of a  user-level context-switching.
132A feature similar to this idea might exist for hardware transactional-memory.
133A significant effort was made to make this approach work but its complexity, lack of robustness, and performance costs resulted in its rejection.
134
135\paragraph{1:1 model}
136This design is the T:H model with T = H, where there is one thread-local heap for each KT.
137(See \VRef[Figure]{f:THSharedHeaps} but with a heap bucket per KT and no bucket or local-pool lock.)
138Hence, immediately after a KT starts, its heap is created and just before a KT terminates, its heap is (logically) deleted.
139Heaps are uncontended for a KTs memory operations to its heap (modulo operations on the global pool and ownership).
140
141Problems:
142\begin{itemize}
143\item
144Need to know when a KT is starts/terminates to create/delete its heap.
145
146\noindent
147It is possible to leverage constructors/destructors for thread-local objects to get a general handle on when a KT starts/terminates.
148\item
149There is a classic \newterm{memory-reclamation} problem for ownership because storage passed to another thread can be returned to a terminated heap.
150
151\noindent
152The classic solution only deletes a heap after all referents are returned, which is complex.
153The cheap alternative is for heaps to persist for program duration to handle outstanding referent frees.
154If old referents return storage to a terminated heap, it is handled in the same way as an active heap.
155To 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).
156In 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.
157\item
158There can be significant external fragmentation as the number of KTs increases.
159
160\noindent
161In many concurrent applications, good performance is achieved with the number of KTs proportional to the number of CPUs.
162Since 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.
163\item
164There is the same serially-reusable problem with UTs migrating across KTs.
165\end{itemize}
166Tests 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.
167
168
169\vspace{5pt}
170\noindent
171The conclusion from this design exercise is: any atomic fence, atomic instruction (lock free), or lock along the allocation fastpath produces significant slowdown.
172For 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.
173For the T:H=CPU and 1:1 models, locking is eliminated along the allocation fastpath.
174However, T:H=CPU has poor operating-system support to determine the CPU id (heap id) and prevent the serially-reusable problem for KTs.
175More operating system support is required to make this model viable, but there is still the serially-reusable problem with user-level threading.
176Leaving the 1:1 model with no atomic actions along the fastpath and no special operating-system support required.
177The 1:1 model still has the serially-reusable problem with user-level threading, which is addressed in \VRef{}, and the greatest potential for heap blowup for certain allocation patterns.
178
179
180% \begin{itemize}
181% \item
182% 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.
183% \item
184% 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.
185% \item
186% 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.
187% 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.
188% \end{itemize}
189% Of the four designs for a low-latency memory allocator, the 1:1 model was chosen for the following reasons:
190
191% \subsection{Advantages of distributed design}
192%
193% The distributed design of llheap is concurrent to work in multi-threaded applications.
194% Some key benefits of the distributed design of llheap are as follows:
195% \begin{itemize}
196% \item
197% 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.
198% \item
199% Low or almost no contention on heap resources.
200% \item
201% It is possible to use sharing and stealing techniques to share/find unused storage, when a free list is unused or empty.
202% \item
203% Distributed design avoids unnecessary locks on resources shared across all KTs.
204% \end{itemize}
205
206\subsection{Allocation Latency}
207
208A primary goal of llheap is low latency.
209Two forms of latency are internal and external.
210Internal latency is the time to perform an allocation, while external latency is time to obtain/return storage from/to the operating system.
211Ideally latency is $O(1)$ with a small constant.
212
213To obtain $O(1)$ internal latency means no searching on the allocation fastpath, largely prohibits coalescing, which leads to external fragmentation.
214The 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).
215
216To 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.
217Excluding real-time operating-systems, operating-system operations are unbounded, and hence some external latency is unavoidable.
218The 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@ \VRef{}).
219Furthermore, while operating-system calls are unbounded, many are now reasonably fast, so their latency is tolerable and infrequent.
220
221
222%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
223
224\section{llheap Structure}
225
226\VRef[Figure]{f:llheapStructure} shows the design of llheap, which uses the following features:
227\begin{itemize}
228\item
2291:1 multiple-heap model to minimize the fastpath,
230\item
231can be built with or without heap ownership,
232\item
233headers per allocation versus containers,
234\item
235no coalescing to minimize latency,
236\item
237global heap memory (pool) obtained from the operating system using @mmap@ to create and reuse heaps needed by threads,
238\item
239local reserved memory (pool) per heap obtained from global pool,
240\item
241global reserved memory (pool) obtained from the operating system using @sbrk@ call,
242\item
243optional fast-lookup table for converting allocation requests into bucket sizes,
244\item
245optional statistic-counters table for accumulating counts of allocation operations.
246\end{itemize}
247
248\begin{figure}
249\centering
250% \includegraphics[width=0.65\textwidth]{figures/NewHeapStructure.eps}
251\input{llheap}
252\caption{llheap Structure}
253\label{f:llheapStructure}
254\end{figure}
255
256llheap 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.
257There is a global bump-pointer to the next free heap in the array.
258When this array is exhausted, another array is allocated.
259There is a global top pointer for a heap intrusive link to chain free heaps from terminated threads.
260When 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@.
261
262When a KT starts, a heap is allocated from the current array for exclusive use by the KT.
263When a KT terminates, its heap is chained onto the heap free-list for reuse by a new KT, which prevents unbounded growth of heaps.
264The free heaps is a stack so hot storage is reused first.
265Preserving all heaps created during the program lifetime, solves the storage lifetime problem, when ownership is used.
266This approach wastes storage if a large number of KTs are created/terminated at program start and then the program continues sequentially.
267llheap 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.
268
269Each heap uses segregated free-buckets that have free objects distributed across 91 different sizes from 16 to 4M.
270The 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.
271Each free bucket of a specific size has the following two lists:
272\begin{itemize}
273\item
274A free stack used solely by the KT heap-owner, so push/pop operations do not require locking.
275The free objects are a stack so hot storage is reused first.
276\item
277For ownership, a shared away-stack for KTs to return storage allocated by other KTs, so push/pop operations require locking.
278When the free stack is empty, the entire ownership stack is removed and becomes the head of the corresponding free stack.
279\end{itemize}
280
281Algorithm~\ref{alg:heapObjectAlloc} shows the allocation outline for an object of size $S$.
282First, the allocation is divided into small (@sbrk@) or large (@mmap@).
283For large allocations, the storage is mapped directly from the operating system.
284For small allocations, $S$ is quantized into a bucket size.
285Quantizing is performed using a binary search over the ordered bucket array.
286An 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.
287(Type @char@ restricts the number of bucket sizes to 256.)
288For $S$ > 64K, a binary search is used.
289Then, the allocation storage is obtained from the following locations (in order), with increasing latency.
290\begin{enumerate}[topsep=0pt,itemsep=0pt,parsep=0pt]
291\item
292bucket's free stack,
293\item
294bucket's away stack,
295\item
296heap's local pool
297\item
298global pool
299\item
300operating system (@sbrk@)
301\end{enumerate}
302
303\begin{figure}
304\vspace*{-10pt}
305\begin{algorithm}[H]
306\small
307\caption{Dynamic object allocation of size $S$}\label{alg:heapObjectAlloc}
308\begin{algorithmic}[1]
309\State $\textit{O} \gets \text{NULL}$
310\If {$S >= \textit{mmap-threshhold}$}
311        \State $\textit{O} \gets \text{allocate dynamic memory using system call mmap with size S}$
312\Else
313        \State $\textit{B} \gets \text{smallest free-bucket} \geq S$
314        \If {$\textit{B's free-list is empty}$}
315                \If {$\textit{B's away-list is empty}$}
316                        \If {$\textit{heap's allocation buffer} < S$}
317                                \State $\text{get allocation from global pool (which might call \lstinline{sbrk})}$
318                        \EndIf
319                        \State $\textit{O} \gets \text{bump allocate an object of size S from allocation buffer}$
320                \Else
321                        \State $\textit{merge B's away-list into free-list}$
322                        \State $\textit{O} \gets \text{pop an object from B's free-list}$
323                \EndIf
324        \Else
325                \State $\textit{O} \gets \text{pop an object from B's free-list}$
326        \EndIf
327        \State $\textit{O's owner} \gets \text{B}$
328\EndIf
329\State $\Return \textit{ O}$
330\end{algorithmic}
331\end{algorithm}
332
333\vspace*{-15pt}
334\begin{algorithm}[H]
335\small
336\caption{Dynamic object free at address $A$ with object ownership}\label{alg:heapObjectFreeOwn}
337\begin{algorithmic}[1]
338\If {$\textit{A mapped allocation}$}
339        \State $\text{return A's dynamic memory to system using system call \lstinline{munmap}}$
340\Else
341        \State $\text{B} \gets \textit{O's owner}$
342        \If {$\textit{B is thread-local heap's bucket}$}
343                \State $\text{push A to B's free-list}$
344        \Else
345                \State $\text{push A to B's away-list}$
346        \EndIf
347\EndIf
348\end{algorithmic}
349\end{algorithm}
350
351\vspace*{-15pt}
352\begin{algorithm}[H]
353\small
354\caption{Dynamic object free at address $A$ without object ownership}\label{alg:heapObjectFreeNoOwn}
355\begin{algorithmic}[1]
356\If {$\textit{A mapped allocation}$}
357        \State $\text{return A's dynamic memory to system using system call \lstinline{munmap}}$
358\Else
359        \State $\text{B} \gets \textit{O's owner}$
360        \If {$\textit{B is thread-local heap's bucket}$}
361                \State $\text{push A to B's free-list}$
362        \Else
363                \State $\text{C} \gets \textit{thread local heap's bucket with same size as B}$
364                \State $\text{push A to C's free-list}$
365        \EndIf
366\EndIf
367\end{algorithmic}
368\end{algorithm}
369\end{figure}
370
371Algorithm~\ref{alg:heapObjectFreeOwn} shows the de-allocation (free) outline for an object at address $A$ with ownership.
372First, the address is divided into small (@sbrk@) or large (@mmap@).
373For large allocations, the storage is unmapped back to the operating system.
374For small allocations, the bucket associated with the request size is retrieved.
375If the bucket is local to the thread, the allocation is pushed onto the thread's associated bucket.
376If the bucket is not local to the thread, the allocation is pushed onto the owning thread's associated away stack.
377
378Algorithm~\ref{alg:heapObjectFreeNoOwn} shows the de-allocation (free) outline for an object at address $A$ without ownership.
379The algorithm is the same as for ownership except if the bucket is not local to the thread.
380Then the corresponding bucket of the owner thread is computed for the deallocating thread, and the allocation is pushed onto the deallocating thread's bucket.
381
382Finally, 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.
383Other 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.
384This design simplifies heap-management code during development and maintenance.
385
386
387\subsection{Alignment}
388
389All dynamic memory allocations must have a minimum storage alignment for the contained object(s).
390Often 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).
391In general, the minimum storage alignment is 8/16-byte boundary on 32/64-bit computers.
392For consistency, the object header is normally aligned at this same boundary.
393Larger alignments must be a power of 2, such page alignment (4/8K).
394Any alignment request, N, $\le$ the minimum alignment is handled as a normal allocation with minimal alignment.
395
396For 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'@.
397\begin{center}
398\input{Alignment1}
399\end{center}
400The storage between @E@ and @H@ is chained onto the appropriate free list for future allocations.
401This 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.
402In 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.
403However, if there are a large number of aligned requests, this approach leads to memory fragmentation from the small free areas around the aligned object.
404As well, it does not work for large allocations, where many memory allocators switch from program @sbrk@ to operating-system @mmap@.
405The 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.
406Finally, 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.
407
408Instead, 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:
409\begin{center}
410\input{Alignment2}
411\end{center}
412The 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.
413The 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@.
414For this special case, there is @alignment - M@ bytes of unused storage after the data object, which subsequently can be used by @realloc@.
415
416Note, the address returned is @A@, which is subsequently returned to @free@.
417However, to correctly free the allocated object, the value @P@ must be computable, since that is the value generated by @malloc@ and returned within @memalign@.
418Hence, there must be a mechanism to detect when @P@ $\neq$ @A@ and how to compute @P@ from @A@.
419
420The llheap approach uses two headers:
421the \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.:
422\begin{center}
423\input{Alignment2Impl}
424\end{center}
425Since @malloc@ has a minimum alignment of @M@, @P@ $\neq$ @A@ only holds for alignments of @M@ or greater.
426When @P@ $\neq$ @A@, the minimum distance between @P@ and @A@ is @M@ bytes, due to the pessimistic storage-allocation.
427Therefore, there is always room for an @M@-byte fake header before @A@.
428
429The fake header must supply an indicator to distinguish it from a normal header and the location of address @P@ generated by @malloc@.
430This information is encoded as an offset from A to P and the initialize alignment (discussed in \VRef{s:ReallocStickyProperties}).
431To 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.
432\begin{center}
433\input{FakeHeader}
434\end{center}
435
436
437\subsection{\lstinline{realloc} and Sticky Properties}
438\label{s:ReallocStickyProperties}
439
440Allocation 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.
441\begin{flushleft}
442\begin{tabular}{ll}
443\multicolumn{1}{c}{\textbf{realloc pattern}} & \multicolumn{1}{c}{\textbf{manually}} \\
444\begin{lstlisting}
445T * naddr = realloc( oaddr, newSize );
446
447
448
449\end{lstlisting}
450&
451\begin{lstlisting}
452T * naddr = (T *)malloc( newSize ); $\C[2.4in]{// new storage}$
453memcpy( naddr, addr, oldSize );  $\C{// copy old bytes}$
454free( addr );                           $\C{// free old storage}$
455addr = naddr;                           $\C{// change pointer}\CRT$
456\end{lstlisting}
457\end{tabular}
458\end{flushleft}
459The realloc pattern leverages available storage at the end of an allocation due to bucket sizes, possibly eliminating a new allocation and copying.
460This pattern is not used enough to reduce storage management costs.
461In fact, if @oaddr@ is @nullptr@, @realloc@ does a @malloc@, so even the initial @malloc@ can be a @realloc@ for consistency in the pattern.
462
463The hidden problem for this pattern is the effect of zero fill and alignment with respect to reallocation.
464Are these properties transient or persistent (``sticky'')?
465For 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.
466That is, if @realloc@ logically extends storage into unused bucket space or allocates new storage to satisfy a size change, are initial allocation properties preserve?
467Currently, 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.
468This silent problem is unintuitive to programmers and difficult to locate because it is transient.
469To 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.
470This change makes the realloc pattern efficient and safe.
471
472
473\subsection{Header}
474
475To preserve allocation properties requires storing additional information with an allocation,
476The only available location is the header, where \VRef[Figure]{f:llheapNormalHeader} shows the llheap storage layout.
477The header has two data field sized appropriately for 32/64-bit alignment requirements.
478The first field is a union of three values:
479\begin{description}
480\item[bucket pointer]
481is 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).
482\item[mapped size]
483is for mapped storage and is the storage size for use in unmapping.
484\item[next free block]
485is for free storage and is an intrusive pointer chaining same-size free blocks onto a bucket's free stack.
486\end{description}
487The second field remembers the request size versus the allocation (bucket) size, \eg request 42 bytes which is rounded up to 64 bytes.
488Since programmers think in request sizes rather than allocation sizes, the request size allows better generation of statistics or errors.
489
490\begin{figure}
491\centering
492\input{Header}
493\caption{llheap Normal Header}
494\label{f:llheapNormalHeader}
495\end{figure}
496
497The 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.
498The 3 unused bits are used to represent mapped allocation, zero filled, and alignment, respectively.
499Note, the alignment bit is not used in the normal header and the zero-filled/mapped bits are not used in the fake header.
500This implementation allows a fast test if any of the lower 3-bits are on (@&@ and compare).
501If no bits are on, it implies a basic allocation, which is handled quickly;
502otherwise, the bits are analysed and appropriate actions are taken for the complex cases.
503Since most allocations are basic, this implementation results in a significant performance gain along the allocation and free fastpath.
504
505
506\section{Statistics and Debugging Modes}
507
508llheap can be built to accumulate fast and largely contention-free allocation statistics to help understand allocation behaviour.
509Incrementing statistic counters must appear on the allocation fastpath.
510As noted, any atomic operation along the fastpath produces a significant increase in allocation costs.
511To 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.
512
513To locate all statistic counters, heaps are linked together in statistics mode, and this list is locked and traversed to sum all counters across heaps.
514Note, the list is locked to prevent errors traversing an active list;
515the statistics counters are not locked and can flicker during accumulation, which is not an issue with atomic read/write.
516\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.
517No other memory allocator studied provides as comprehensive statistical information.
518Finally, these statistics were invaluable during the development of this thesis for debugging and verifying correctness, and hence, should be equally valuable to application developers.
519
520\begin{figure}
521\begin{lstlisting}
522Heap statistics: (storage request / allocation)
523  malloc >0 calls 2,766; 0 calls 2,064; storage 12,715 / 13,367 bytes
524  aalloc >0 calls 0; 0 calls 0; storage 0 / 0 bytes
525  calloc >0 calls 6; 0 calls 0; storage 1,008 / 1,104 bytes
526  memalign >0 calls 0; 0 calls 0; storage 0 / 0 bytes
527  amemalign >0 calls 0; 0 calls 0; storage 0 / 0 bytes
528  cmemalign >0 calls 0; 0 calls 0; storage 0 / 0 bytes
529  resize >0 calls 0; 0 calls 0; storage 0 / 0 bytes
530  realloc >0 calls 0; 0 calls 0; storage 0 / 0 bytes
531  free !null calls 2,766; null calls 4,064; storage 12,715 / 13,367 bytes
532  away pulls 0; pushes 0; storage 0 / 0 bytes
533  sbrk calls 1; storage 10,485,760 bytes
534  mmap calls 10,000; storage 10,000 / 10,035 bytes
535  munmap calls 10,000; storage 10,000 / 10,035 bytes
536  threads started 4; exited 3
537  heaps new 4; reused 0
538\end{lstlisting}
539\caption{Statistics Output}
540\label{f:StatiticsOutput}
541\end{figure}
542
543llheap can also be built with debug checking, which inserts many asserts along all allocation paths.
544These assertions detect incorrect allocation usage, like double frees, unfreed storage, or memory corruptions because internal values (like header fields) are overwritten.
545These checks are best effort as opposed to complete allocation checking as in @valgrind@.
546Nevertheless, the checks detect many allocation problems.
547There 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.
548For example, @printf@ allocates a 1024 buffer on first call and never deletes this buffer.
549To prevent a false positive for unfreed storage, it is possible to specify an amount of storage that is never freed (see \VRef{}), and it is subtracted from the total allocate/free difference.
550Determining the amount of never-freed storage is annoying, but once done, any warnings of unfreed storage are application related.
551
552Tests 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.
553
554
555\section{User-level Threading Support}
556
557The 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.
558The solution is to prevent interrupts that can result in CPU or KT change during operations that are logically critical sections.
559Locking these critical sections negates any attempt for a quick fastpath and results in high contention.
560For 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.
561Without time slicing, a user thread performing a long computation can prevent execution (starve) other threads.
562To 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.
563The 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.
564
565llheap 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.
566On 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.
567On the fastpath, disabling/enabling interrupts is too expensive as accessing thread-local storage can be expensive and not thread-safe.
568For example, the ARM processor stores the thread-local pointer in a coprocessor register that cannot perform atomic base-displacement addressing.
569Hence, 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.
570
571The fast technique defines a special code section and places all non-interruptible routines in this section.
572The linker places all code in this section into a contiguous block of memory, but the order of routines within the block is unspecified.
573Then, 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.
574This 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.
575Hence, for correctness, this approach requires inspection of generated assembler code for routines placed in the non-interruptible section.
576This 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.
577These techniques are used in both the \uC and \CFA versions of llheap, where both of these systems have user-level threading.
578
579
580\section{Bootstrapping}
581
582There are problems bootstrapping a memory allocator.
583\begin{enumerate}
584\item
585Programs can be statically or dynamically linked.
586\item
587The order the linker schedules startup code is poorly supported.
588\item
589Knowing a KT's start and end independently from the KT code is difficult.
590\end{enumerate}
591
592For static linking, the allocator is loaded with the program.
593Hence, allocation calls immediately invoke the allocator operation defined by the loaded allocation library and there is only one memory allocator used in the program.
594This approach allows allocator substitution by placing an allocation library before any other in the linked/load path.
595
596Allocator 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.
597As 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.
598Hence, some part of the @sbrk@ area may be used by the default allocator and statistics about allocation operations cannot be correct.
599Furthermore, dynamic linking goes through trampolines, so there is an additional cost along the allocator fastpath for all allocation operations.
600Testing 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.
601
602All allocator libraries need to perform startup code to initialize data structures, such as the heap array for llheap.
603The problem is getting initialized done before the first allocator call.
604However, 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.
605As a result, calls to allocation routines occur without initialization.
606To deal with this problem, it is necessary to put a conditional initialization check along the allocation fastpath to trigger initialization (singleton pattern).
607
608Two other important execution points are program startup and termination, which include prologue or epilogue code to bootstrap a program, which programmers are unaware of.
609For example, dynamic-memory allocations before/after the application starts should not be considered in statistics because the application does not make these calls.
610llheap establishes these two points using routines:
611\begin{lstlisting}
612__attribute__(( constructor( 100 ) )) static void startup( void ) {
613        // clear statistic counters
614        // reset allocUnfreed counter
615}
616__attribute__(( destructor( 100 ) )) static void shutdown( void ) {
617        // sum allocUnfreed for all heaps
618        // subtract global unfreed storage
619        // if allocUnfreed > 0 then print warning message
620}
621\end{lstlisting}
622which use global constructor/destructor priority 100, where the linker calls these routines at program prologue/epilogue in increasing/decreasing order of priority.
623Application programs may only use global constructor/destructor priorities greater than 100.
624Hence, @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.
625By resetting counters in @startup@, prologue allocations are ignored, and checking unfreed storage in @shutdown@ checks only application memory management, ignoring the program epilogue.
626
627While @startup@/@shutdown@ apply to the program KT, a concurrent program creates additional KTs that do not trigger these routines.
628However, it is essential for the allocator to know when each KT is started/terminated.
629One 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.
630\begin{lstlisting}
631struct ThreadManager {
632        volatile bool pgm_thread;
633        ThreadManager() {} // unusable
634        ~ThreadManager() { if ( pgm_thread ) heapManagerDtor(); }
635};
636static thread_local ThreadManager threadManager;
637\end{lstlisting}
638Unfortunately, thread-local variables are created lazily, \ie on the first dereference of @threadManager@, which then triggers its constructor.
639Therefore, 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.
640Fortunately, 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.
641Now 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.
642The conditional destructor call prevents closing down the program heap, which must remain available because epilogue code may free more storage.
643
644Finally, 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.
645This recursion is handled with another thread-local flag to prevent double initialization.
646A 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@.
647In 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.
648
649For 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.
650The following API was created to provide interaction between the language runtime and the allocator.
651\begin{lstlisting}
652void startTask();                       $\C{// KT starts}$
653void finishTask();                      $\C{// KT ends}$
654void startup();                         $\C{// when application code starts}$
655void shutdown();                        $\C{// when application code ends}$
656bool traceHeap();                       $\C{// enable allocation/free printing for debugging}$
657bool traceHeapOn();                     $\C{// start printing allocation/free calls}$
658bool traceHeapOff();                    $\C{// stop printing allocation/free calls}$
659\end{lstlisting}
660This kind of API is necessary to allow concurrent runtime systems to interact with difference memory allocators in a consistent way.
661
662%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
663
664\section{Added Features and Methods}
665
666The C dynamic-allocation API (see \VRef[Figure]{f:CDynamicAllocationAPI}) is neither orthogonal nor complete.
667For example,
668\begin{itemize}
669\item
670It is possible to zero fill or align an allocation but not both.
671\item
672It is \emph{only} possible to zero fill and array allocation.
673\item
674It is not possible to resize a memory allocation without data copying.
675\item
676@realloc@ does not preserve initial allocation properties.
677\end{itemize}
678As a result, programmers must provide these options, which is error prone, resulting in blaming the entire programming language for a poor dynamic-allocation API.
679Furthermore, newer programming languages have better type systems that can provide safer and more powerful APIs for memory allocation.
680
681\begin{figure}
682\begin{lstlisting}
683void * malloc( size_t size );
684void * calloc( size_t nmemb, size_t size );
685void * realloc( void * ptr, size_t size );
686void * reallocarray( void * ptr, size_t nmemb, size_t size );
687void free( void * ptr );
688void * memalign( size_t alignment, size_t size );
689void * valloc( size_t size );
690void * pvalloc( size_t size );
691struct mallinfo mallinfo( void );
692int mallopt( int param, int val );
693int malloc_trim( size_t pad );
694size_t malloc_usable_size( void * ptr );
695void malloc_stats( void );
696int malloc_info( int options, FILE * fp );
697\end{lstlisting}
698\caption{C Dynamic-Allocation API}
699\label{f:CDynamicAllocationAPI}
700\end{figure}
701
702The following presents design and API changes for C, \CC (\uC), and \CFA, all of which are implemented in llheap.
703
704
705\subsection{Out of Memory}
706
707Most allocators use @nullptr@ to indicate an allocation failure, specifically out of memory;
708hence the need to return an alternate value for a zero-sized allocation.
709The alternative is to abort a program when out of memory.
710In theory, notifying the programmer allows recovery;
711in practice, it is almost impossible to gracefully recover when out of memory, so the cheaper approach of returning @nullptr@ for a zero-sized allocation is chosen for llheap.
712
713
714\subsection{C Interface}
715
716Within the C type-system, it is still possible to increase orthogonality and functionality of the dynamic-memory API to make the allocator more usable for programmers.
717
718\paragraph{\lstinline{void * aalloc( size_t dim, size_t elemSize )}}
719@aalloc@ is an extension of malloc.
720It allows programmer to allocate a dynamic array of objects without calculating the total size of array explicitly.
721The only alternate of this routine in the other allocators is @calloc@ but @calloc@ also fills the dynamic memory with 0 which makes it slower for a programmer who only wants to dynamically allocate an array of objects without filling it with 0.
722\paragraph{Usage}
723@aalloc@ takes two parameters.
724
725\begin{itemize}
726\item
727@dim@: number of objects in the array
728\item
729@elemSize@: size of the object in the array.
730\end{itemize}
731It returns address of dynamic object allocated on heap that can contain dim number of objects of the size elemSize.
732On failure, it returns a @NULL@ pointer.
733
734\paragraph{\lstinline{void * resize( void * oaddr, size_t size )}}
735@resize@ is an extension of relloc.
736It allows programmer to reuse a currently allocated dynamic object with a new size requirement.
737Its alternate in the other allocators is @realloc@ but relloc also copy the data in old object to the new object which makes it slower for the programmer who only wants to reuse an old dynamic object for a new size requirement but does not want to preserve the data in the old object to the new object.
738\paragraph{Usage}
739@resize@ takes two parameters.
740
741\begin{itemize}
742\item
743@oaddr@: the address of the old object that needs to be resized.
744\item
745@size@: the new size requirement of the to which the old object needs to be resized.
746\end{itemize}
747It returns an object that is of the size given but it does not preserve the data in the old object.
748On failure, it returns a @NULL@ pointer.
749
750\paragraph{\lstinline{void * resize( void * oaddr, size_t nalign, size_t size )}}
751This @resize@ is an extension of the above @resize@ (FIX ME: cite above resize).
752In addition to resizing the size of of an old object, it can also realign the old object to a new alignment requirement.
753\paragraph{Usage}
754This resize takes three parameters.
755It takes an additional parameter of nalign as compared to the above resize (FIX ME: cite above resize).
756
757\begin{itemize}
758\item
759@oaddr@: the address of the old object that needs to be resized.
760\item
761@nalign@: the new alignment to which the old object needs to be realigned.
762\item
763@size@: the new size requirement of the to which the old object needs to be resized.
764\end{itemize}
765It returns an object with the size and alignment given in the parameters.
766On failure, it returns a @NULL@ pointer.
767
768\paragraph{\lstinline{void * amemalign( size_t alignment, size_t dim, size_t elemSize )}}
769amemalign is a hybrid of memalign and aalloc.
770It allows programmer to allocate an aligned dynamic array of objects without calculating the total size of the array explicitly.
771It frees the programmer from calculating the total size of the array.
772\paragraph{Usage}
773amemalign takes three parameters.
774
775\begin{itemize}
776\item
777@alignment@: the alignment to which the dynamic array needs to be aligned.
778\item
779@dim@: number of objects in the array
780\item
781@elemSize@: size of the object in the array.
782\end{itemize}
783It returns a dynamic array of objects that has the capacity to contain dim number of objects of the size of elemSize.
784The returned dynamic array is aligned to the given alignment.
785On failure, it returns a @NULL@ pointer.
786
787\paragraph{\lstinline{void * cmemalign( size_t alignment, size_t dim, size_t elemSize )}}
788cmemalign is a hybrid of amemalign and calloc.
789It allows programmer to allocate an aligned dynamic array of objects that is 0 filled.
790The current way to do this in other allocators is to allocate an aligned object with memalign and then fill it with 0 explicitly.
791This routine provides both features of aligning and 0 filling, implicitly.
792\paragraph{Usage}
793cmemalign takes three parameters.
794
795\begin{itemize}
796\item
797@alignment@: the alignment to which the dynamic array needs to be aligned.
798\item
799@dim@: number of objects in the array
800\item
801@elemSize@: size of the object in the array.
802\end{itemize}
803It returns a dynamic array of objects that has the capacity to contain dim number of objects of the size of elemSize.
804The returned dynamic array is aligned to the given alignment and is 0 filled.
805On failure, it returns a @NULL@ pointer.
806
807\paragraph{\lstinline{size_t malloc_alignment( void * addr )}}
808@malloc_alignment@ returns the alignment of a currently allocated dynamic object.
809It allows the programmer in memory management and personal bookkeeping.
810It helps the programmer in verifying the alignment of a dynamic object especially in a scenario similar to producer-consumer where a producer allocates a dynamic object and the consumer needs to assure that the dynamic object was allocated with the required alignment.
811\paragraph{Usage}
812@malloc_alignment@ takes one parameters.
813
814\begin{itemize}
815\item
816@addr@: the address of the currently allocated dynamic object.
817\end{itemize}
818@malloc_alignment@ returns the alignment of the given dynamic object.
819On failure, it return the value of default alignment of the llheap allocator.
820
821\paragraph{\lstinline{bool malloc_zero_fill( void * addr )}}
822@malloc_zero_fill@ returns whether a currently allocated dynamic object was initially zero filled at the time of allocation.
823It allows the programmer in memory management and personal bookkeeping.
824It helps the programmer in verifying the zero filled property of a dynamic object especially in a scenario similar to producer-consumer where a producer allocates a dynamic object and the consumer needs to assure that the dynamic object was zero filled at the time of allocation.
825\paragraph{Usage}
826@malloc_zero_fill@ takes one parameters.
827
828\begin{itemize}
829\item
830@addr@: the address of the currently allocated dynamic object.
831\end{itemize}
832@malloc_zero_fill@ returns true if the dynamic object was initially zero filled and return false otherwise.
833On failure, it returns false.
834
835\paragraph{\lstinline{size_t malloc_size( void * addr )}}
836@malloc_size@ returns the request size of a currently allocated dynamic object.
837It allows the programmer in memory management and personal bookkeeping.
838It helps the programmer in verifying the alignment of a dynamic object especially in a scenario similar to producer-consumer where a producer allocates a dynamic object and the consumer needs to assure that the dynamic object was allocated with the required size.
839Its current alternate in the other allocators is @malloc_usable_size@.
840But, @malloc_size@ is different from @malloc_usable_size@ as @malloc_usabe_size@ returns the total data capacity of dynamic object including the extra space at the end of the dynamic object.
841On the other hand, @malloc_size@ returns the size that was given to the allocator at the allocation of the dynamic object.
842This size is updated when an object is realloced, resized, or passed through a similar allocator routine.
843\paragraph{Usage}
844@malloc_size@ takes one parameters.
845
846\begin{itemize}
847\item
848@addr@: the address of the currently allocated dynamic object.
849\end{itemize}
850@malloc_size@ returns the request size of the given dynamic object.
851On failure, it return zero.
852
853
854\subsection{\CC Interface}
855
856\paragraph{\lstinline{void * realloc( void * oaddr, size_t nalign, size_t size )}}
857This @realloc@ is an extension of the default @realloc@ (FIX ME: cite default @realloc@).
858In addition to reallocating an old object and preserving the data in old object, it can also realign the old object to a new alignment requirement.
859\paragraph{Usage}
860This @realloc@ takes three parameters.
861It takes an additional parameter of nalign as compared to the default @realloc@.
862
863\begin{itemize}
864\item
865@oaddr@: the address of the old object that needs to be reallocated.
866\item
867@nalign@: the new alignment to which the old object needs to be realigned.
868\item
869@size@: the new size requirement of the to which the old object needs to be resized.
870\end{itemize}
871It returns an object with the size and alignment given in the parameters that preserves the data in the old object.
872On failure, it returns a @NULL@ pointer.
873
874
875\subsection{\CFA Interface}
876We added some routines to the @malloc@ interface of \CFA.
877These routines can only be used in \CFA and not in our stand-alone llheap allocator as these routines use some features that are only provided by \CFA and not by C.
878It makes the allocator even more usable to the programmers.
879\CFA provides the liberty to know the returned type of a call to the allocator.
880So, mainly in these added routines, we removed the object size parameter from the routine as allocator can calculate the size of the object from the returned type.
881
882\subsection{\lstinline{T * malloc( void )}}
883This @malloc@ is a simplified polymorphic form of default @malloc@ (FIX ME: cite malloc).
884It does not take any parameter as compared to default @malloc@ that takes one parameter.
885\paragraph{Usage}
886This @malloc@ takes no parameters.
887It returns a dynamic object of the size of type @T@.
888On failure, it returns a @NULL@ pointer.
889
890\subsection{\lstinline{T * aalloc( size_t dim )}}
891This @aalloc@ is a simplified polymorphic form of above @aalloc@ (FIX ME: cite aalloc).
892It takes one parameter as compared to the above @aalloc@ that takes two parameters.
893\paragraph{Usage}
894aalloc takes one parameters.
895
896\begin{itemize}
897\item
898@dim@: required number of objects in the array.
899\end{itemize}
900It returns a dynamic object that has the capacity to contain dim number of objects, each of the size of type @T@.
901On failure, it returns a @NULL@ pointer.
902
903\subsection{\lstinline{T * calloc( size_t dim )}}
904This @calloc@ is a simplified polymorphic form of default @calloc@ (FIX ME: cite calloc).
905It takes one parameter as compared to the default @calloc@ that takes two parameters.
906\paragraph{Usage}
907This @calloc@ takes one parameter.
908
909\begin{itemize}
910\item
911@dim@: required number of objects in the array.
912\end{itemize}
913It returns a dynamic object that has the capacity to contain dim number of objects, each of the size of type @T@.
914On failure, it returns a @NULL@ pointer.
915
916\subsection{\lstinline{T * resize( T * ptr, size_t size )}}
917This resize is a simplified polymorphic form of above resize (FIX ME: cite resize with alignment).
918It takes two parameters as compared to the above resize that takes three parameters.
919It frees the programmer from explicitly mentioning the alignment of the allocation as \CFA provides gives allocator the liberty to get the alignment of the returned type.
920\paragraph{Usage}
921This resize takes two parameters.
922
923\begin{itemize}
924\item
925@ptr@: address of the old object.
926\item
927@size@: the required size of the new object.
928\end{itemize}
929It returns a dynamic object of the size given in parameters.
930The returned object is aligned to the alignment of type @T@.
931On failure, it returns a @NULL@ pointer.
932
933\subsection{\lstinline{T * realloc( T * ptr, size_t size )}}
934This @realloc@ is a simplified polymorphic form of default @realloc@ (FIX ME: cite @realloc@ with align).
935It takes two parameters as compared to the above @realloc@ that takes three parameters.
936It frees the programmer from explicitly mentioning the alignment of the allocation as \CFA provides gives allocator the liberty to get the alignment of the returned type.
937\paragraph{Usage}
938This @realloc@ takes two parameters.
939
940\begin{itemize}
941\item
942@ptr@: address of the old object.
943\item
944@size@: the required size of the new object.
945\end{itemize}
946It returns a dynamic object of the size given in parameters that preserves the data in the given object.
947The returned object is aligned to the alignment of type @T@.
948On failure, it returns a @NULL@ pointer.
949
950\subsection{\lstinline{T * memalign( size_t align )}}
951This memalign is a simplified polymorphic form of default memalign (FIX ME: cite memalign).
952It takes one parameters as compared to the default memalign that takes two parameters.
953\paragraph{Usage}
954memalign takes one parameters.
955
956\begin{itemize}
957\item
958@align@: the required alignment of the dynamic object.
959\end{itemize}
960It returns a dynamic object of the size of type @T@ that is aligned to given parameter align.
961On failure, it returns a @NULL@ pointer.
962
963\subsection{\lstinline{T * amemalign( size_t align, size_t dim )}}
964This amemalign is a simplified polymorphic form of above amemalign (FIX ME: cite amemalign).
965It takes two parameter as compared to the above amemalign that takes three parameters.
966\paragraph{Usage}
967amemalign takes two parameters.
968
969\begin{itemize}
970\item
971@align@: required alignment of the dynamic array.
972\item
973@dim@: required number of objects in the array.
974\end{itemize}
975It returns a dynamic object that has the capacity to contain dim number of objects, each of the size of type @T@.
976The returned object is aligned to the given parameter align.
977On failure, it returns a @NULL@ pointer.
978
979\subsection{\lstinline{T * cmemalign( size_t align, size_t dim  )}}
980This cmemalign is a simplified polymorphic form of above cmemalign (FIX ME: cite cmemalign).
981It takes two parameter as compared to the above cmemalign that takes three parameters.
982\paragraph{Usage}
983cmemalign takes two parameters.
984
985\begin{itemize}
986\item
987@align@: required alignment of the dynamic array.
988\item
989@dim@: required number of objects in the array.
990\end{itemize}
991It returns a dynamic object that has the capacity to contain dim number of objects, each of the size of type @T@.
992The returned object is aligned to the given parameter align and is zero filled.
993On failure, it returns a @NULL@ pointer.
994
995\subsection{\lstinline{T * aligned_alloc( size_t align )}}
996This @aligned_alloc@ is a simplified polymorphic form of default @aligned_alloc@ (FIX ME: cite @aligned_alloc@).
997It takes one parameter as compared to the default @aligned_alloc@ that takes two parameters.
998\paragraph{Usage}
999This @aligned_alloc@ takes one parameter.
1000
1001\begin{itemize}
1002\item
1003@align@: required alignment of the dynamic object.
1004\end{itemize}
1005It returns a dynamic object of the size of type @T@ that is aligned to the given parameter.
1006On failure, it returns a @NULL@ pointer.
1007
1008\subsection{\lstinline{int posix_memalign( T ** ptr, size_t align )}}
1009This @posix_memalign@ is a simplified polymorphic form of default @posix_memalign@ (FIX ME: cite @posix_memalign@).
1010It takes two parameters as compared to the default @posix_memalign@ that takes three parameters.
1011\paragraph{Usage}
1012This @posix_memalign@ takes two parameter.
1013
1014\begin{itemize}
1015\item
1016@ptr@: variable address to store the address of the allocated object.
1017\item
1018@align@: required alignment of the dynamic object.
1019\end{itemize}
1020
1021It stores address of the dynamic object of the size of type @T@ in given parameter ptr.
1022This object is aligned to the given parameter.
1023On failure, it returns a @NULL@ pointer.
1024
1025\subsection{\lstinline{T * valloc( void )}}
1026This @valloc@ is a simplified polymorphic form of default @valloc@ (FIX ME: cite @valloc@).
1027It takes no parameters as compared to the default @valloc@ that takes one parameter.
1028\paragraph{Usage}
1029@valloc@ takes no parameters.
1030It returns a dynamic object of the size of type @T@ that is aligned to the page size.
1031On failure, it returns a @NULL@ pointer.
1032
1033\subsection{\lstinline{T * pvalloc( void )}}
1034\paragraph{Usage}
1035@pvalloc@ takes no parameters.
1036It returns a dynamic object of the size that is calculated by rounding the size of type @T@.
1037The returned object is also aligned to the page size.
1038On failure, it returns a @NULL@ pointer.
1039
1040\subsection{Alloc Interface}
1041In addition to improve allocator interface both for \CFA and our stand-alone allocator llheap in C.
1042We also added a new alloc interface in \CFA that increases usability of dynamic memory allocation.
1043This interface helps programmers in three major ways.
1044
1045\begin{itemize}
1046\item
1047Routine Name: alloc interface frees programmers from remembering different routine names for different kind of dynamic allocations.
1048\item
1049Parameter Positions: alloc interface frees programmers from remembering parameter positions in call to routines.
1050\item
1051Object Size: alloc interface does not require programmer to mention the object size as \CFA allows allocator to determine the object size from returned type of alloc call.
1052\end{itemize}
1053
1054Alloc interface uses polymorphism, backtick routines (FIX ME: cite backtick) and ttype parameters of \CFA (FIX ME: cite ttype) to provide a very simple dynamic memory allocation interface to the programmers.
1055The new interface has just one routine name alloc that can be used to perform a wide range of dynamic allocations.
1056The parameters use backtick functions to provide a similar-to named parameters feature for our alloc interface so that programmers do not have to remember parameter positions in alloc call except the position of dimension (dim) parameter.
1057
1058\subsection{Routine: \lstinline{T * alloc( ...
1059)}}
1060Call to alloc without any parameter returns one object of size of type @T@ allocated dynamically.
1061Only the dimension (dim) parameter for array allocation has the fixed position in the alloc routine.
1062If programmer wants to allocate an array of objects that the required number of members in the array has to be given as the first parameter to the alloc routine.
1063alloc routine accepts six kinds of arguments.
1064Using different combinations of than parameters, different kind of allocations can be performed.
1065Any combination of parameters can be used together except @`realloc@ and @`resize@ that should not be used simultaneously in one call to routine as it creates ambiguity about whether to reallocate or resize a currently allocated dynamic object.
1066If both @`resize@ and @`realloc@ are used in a call to alloc then the latter one will take effect or unexpected resulted might be produced.
1067
1068\paragraph{Dim}
1069This is the only parameter in the alloc routine that has a fixed-position and it is also the only parameter that does not use a backtick function.
1070It has to be passed at the first position to alloc call in-case of an array allocation of objects of type @T@.
1071It represents the required number of members in the array allocation as in \CFA's @aalloc@ (FIX ME: cite aalloc).
1072This parameter should be of type @size_t@.
1073
1074Example: @int a = alloc( 5 )@
1075This call will return a dynamic array of five integers.
1076
1077\paragraph{Align}
1078This parameter is position-free and uses a backtick routine align (@`align@).
1079The parameter passed with @`align@ should be of type @size_t@.
1080If the alignment parameter is not a power of two or is less than the default alignment of the allocator (that can be found out using routine libAlign in \CFA) then the passed alignment parameter will be rejected and the default alignment will be used.
1081
1082Example: @int b = alloc( 5 , 64`align )@
1083This call will return a dynamic array of five integers.
1084It will align the allocated object to 64.
1085
1086\paragraph{Fill}
1087This parameter is position-free and uses a backtick routine fill (@`fill@).
1088In case of @realloc@, only the extra space after copying the data in the old object will be filled with given parameter.
1089Three types of parameters can be passed using `fill.
1090
1091\begin{itemize}
1092\item
1093@char@: A char can be passed with @`fill@ to fill the whole dynamic allocation with the given char recursively till the end of required allocation.
1094\item
1095Object of returned type: An object of type of returned type can be passed with @`fill@ to fill the whole dynamic allocation with the given object recursively till the end of required allocation.
1096\item
1097Dynamic object of returned type: A dynamic object of type of returned type can be passed with @`fill@ to fill the dynamic allocation with the given dynamic object.
1098In this case, the allocated memory is not filled recursively till the end of allocation.
1099The filling happen until the end object passed to @`fill@ or the end of requested allocation reaches.
1100\end{itemize}
1101
1102Example: @int b = alloc( 5 , 'a'`fill )@
1103This call will return a dynamic array of five integers.
1104It will fill the allocated object with character 'a' recursively till the end of requested allocation size.
1105
1106Example: @int b = alloc( 5 , 4`fill )@
1107This call will return a dynamic array of five integers.
1108It will fill the allocated object with integer 4 recursively till the end of requested allocation size.
1109
1110Example: @int b = alloc( 5 , a`fill )@ where @a@ is a pointer of int type
1111This call will return a dynamic array of five integers.
1112It will copy data in a to the returned object non-recursively until end of a or the newly allocated object is reached.
1113
1114\paragraph{Resize}
1115This parameter is position-free and uses a backtick routine resize (@`resize@).
1116It represents the old dynamic object (oaddr) that the programmer wants to
1117\begin{itemize}
1118\item
1119resize to a new size.
1120\item
1121realign to a new alignment
1122\item
1123fill with something.
1124\end{itemize}
1125The data in old dynamic object will not be preserved in the new object.
1126The type of object passed to @`resize@ and the returned type of alloc call can be different.
1127
1128Example: @int b = alloc( 5 , a`resize )@
1129This call will resize object a to a dynamic array that can contain 5 integers.
1130
1131Example: @int b = alloc( 5 , a`resize , 32`align )@
1132This call will resize object a to a dynamic array that can contain 5 integers.
1133The returned object will also be aligned to 32.
1134
1135Example: @int b = alloc( 5 , a`resize , 32`align , 2`fill )@
1136This call will resize object a to a dynamic array that can contain 5 integers.
1137The returned object will also be aligned to 32 and will be filled with 2.
1138
1139\paragraph{Realloc}
1140This parameter is position-free and uses a backtick routine @realloc@ (@`realloc@).
1141It represents the old dynamic object (oaddr) that the programmer wants to
1142\begin{itemize}
1143\item
1144realloc to a new size.
1145\item
1146realign to a new alignment
1147\item
1148fill with something.
1149\end{itemize}
1150The data in old dynamic object will be preserved in the new object.
1151The type of object passed to @`realloc@ and the returned type of alloc call cannot be different.
1152
1153Example: @int b = alloc( 5 , a`realloc )@
1154This call will realloc object a to a dynamic array that can contain 5 integers.
1155
1156Example: @int b = alloc( 5 , a`realloc , 32`align )@
1157This call will realloc object a to a dynamic array that can contain 5 integers.
1158The returned object will also be aligned to 32.
1159
1160Example: @int b = alloc( 5 , a`realloc , 32`align , 2`fill )@
1161This call will resize object a to a dynamic array that can contain 5 integers.
1162The returned object will also be aligned to 32.
1163The extra space after copying data of a to the returned object will be filled with 2.
Note: See TracBrowser for help on using the repository browser.