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 <wtf/Noncopyable.h>
29#include <wtf/PrintStream.h>
30
31namespace JSC {
32
33class HeapCell;
34
35struct FreeCell {
36 static uintptr_t scramble(FreeCell* cell, uintptr_t secret)
37 {
38 return bitwise_cast<uintptr_t>(cell) ^ secret;
39 }
40
41 static FreeCell* descramble(uintptr_t cell, uintptr_t secret)
42 {
43 return bitwise_cast<FreeCell*>(cell ^ secret);
44 }
45
46 void setNext(FreeCell* next, uintptr_t secret)
47 {
48 scrambledNext = scramble(next, secret);
49 }
50
51 FreeCell* next(uintptr_t secret) const
52 {
53 return descramble(scrambledNext, secret);
54 }
55
56 uintptr_t scrambledNext;
57};
58
59class FreeList {
60public:
61 FreeList(unsigned cellSize);
62 ~FreeList();
63
64 void clear();
65
66 void initializeList(FreeCell* head, uintptr_t secret, unsigned bytes);
67 void initializeBump(char* payloadEnd, unsigned remaining);
68
69 bool allocationWillFail() const { return !head() && !m_remaining; }
70 bool allocationWillSucceed() const { return !allocationWillFail(); }
71
72 template<typename Func>
73 HeapCell* allocate(const Func& slowPath);
74
75 bool contains(HeapCell*) const;
76
77 template<typename Func>
78 void forEach(const Func&) const;
79
80 unsigned originalSize() const { return m_originalSize; }
81
82 static ptrdiff_t offsetOfScrambledHead() { return OBJECT_OFFSETOF(FreeList, m_scrambledHead); }
83 static ptrdiff_t offsetOfSecret() { return OBJECT_OFFSETOF(FreeList, m_secret); }
84 static ptrdiff_t offsetOfPayloadEnd() { return OBJECT_OFFSETOF(FreeList, m_payloadEnd); }
85 static ptrdiff_t offsetOfRemaining() { return OBJECT_OFFSETOF(FreeList, m_remaining); }
86 static ptrdiff_t offsetOfOriginalSize() { return OBJECT_OFFSETOF(FreeList, m_originalSize); }
87 static ptrdiff_t offsetOfCellSize() { return OBJECT_OFFSETOF(FreeList, m_cellSize); }
88
89 void dump(PrintStream&) const;
90
91 unsigned cellSize() const { return m_cellSize; }
92
93private:
94 FreeCell* head() const { return FreeCell::descramble(m_scrambledHead, m_secret); }
95
96 uintptr_t m_scrambledHead { 0 };
97 uintptr_t m_secret { 0 };
98 char* m_payloadEnd { nullptr };
99 unsigned m_remaining { 0 };
100 unsigned m_originalSize { 0 };
101 unsigned m_cellSize { 0 };
102};
103
104} // namespace JSC
105
106