1/*
2 * Copyright (C) 2016-2017 Apple Inc. All rights reserved.
3 *
4 * Redistribution and use in source and binary forms, with or without
5 * modification, are permitted provided that the following conditions
6 * are met:
7 * 1. Redistributions of source code must retain the above copyright
8 * notice, this list of conditions and the following disclaimer.
9 * 2. Redistributions in binary form must reproduce the above copyright
10 * notice, this list of conditions and the following disclaimer in the
11 * documentation and/or other materials provided with the distribution.
12 *
13 * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
14 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
15 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
16 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR
17 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
18 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
19 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
20 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
21 * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
22 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
23 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
24 */
25
26#pragma once
27
28#include "BExport.h"
29#include <cstddef>
30#include <cstdint>
31
32namespace bmalloc {
33
34class VariadicBumpAllocator;
35
36struct FreeCell {
37 static uintptr_t scramble(FreeCell* cell, uintptr_t secret)
38 {
39 return reinterpret_cast<uintptr_t>(cell) ^ secret;
40 }
41
42 static FreeCell* descramble(uintptr_t cell, uintptr_t secret)
43 {
44 return reinterpret_cast<FreeCell*>(cell ^ secret);
45 }
46
47 void setNext(FreeCell* next, uintptr_t secret)
48 {
49 scrambledNext = scramble(next, secret);
50 }
51
52 FreeCell* next(uintptr_t secret) const
53 {
54 return descramble(scrambledNext, secret);
55 }
56
57 uintptr_t scrambledNext;
58};
59
60class FreeList {
61public:
62 friend class VariadicBumpAllocator;
63
64 BEXPORT FreeList();
65 BEXPORT ~FreeList();
66
67 BEXPORT void clear();
68
69 BEXPORT void initializeList(FreeCell* head, uintptr_t secret, unsigned bytes);
70 BEXPORT void initializeBump(char* payloadEnd, unsigned remaining);
71
72 bool allocationWillFail() const { return !head() && !m_remaining; }
73 bool allocationWillSucceed() const { return !allocationWillFail(); }
74
75 template<typename Config, typename Func>
76 void* allocate(const Func& slowPath);
77
78 bool contains(void*) const;
79
80 template<typename Config, typename Func>
81 void forEach(const Func&) const;
82
83 unsigned originalSize() const { return m_originalSize; }
84
85private:
86 FreeCell* head() const { return FreeCell::descramble(m_scrambledHead, m_secret); }
87
88 uintptr_t m_scrambledHead { 0 };
89 uintptr_t m_secret { 0 };
90 char* m_payloadEnd { nullptr };
91 unsigned m_remaining { 0 };
92 unsigned m_originalSize { 0 };
93};
94
95} // namespace bmalloc
96
97