1/*
2 * Copyright (C) 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 "Bits.h"
29#include "DeferredTrigger.h"
30#include "FreeList.h"
31#include <climits>
32
33namespace bmalloc {
34
35class IsoHeapImplBase;
36template<typename Config> class IsoDirectoryBase;
37template<typename Config> class IsoHeapImpl;
38
39class IsoPageBase {
40public:
41 static constexpr size_t pageSize = 16384;
42
43 explicit IsoPageBase(bool isShared)
44 : m_isShared(isShared)
45 {
46 }
47
48 static IsoPageBase* pageFor(void*);
49
50 bool isShared() const { return m_isShared; }
51
52protected:
53 BEXPORT static void* allocatePageMemory();
54
55 bool m_isShared { false };
56};
57
58template<typename Config>
59class IsoPage : public IsoPageBase {
60public:
61 static constexpr unsigned numObjects = pageSize / Config::objectSize;
62
63 static_assert(numObjects, "IsoHeap size should allow at least one allocation per page");
64
65 static IsoPage* tryCreate(IsoDirectoryBase<Config>& directory, unsigned index);
66
67 // It's expected that you will only use this with placement new and direct destruction.
68 IsoPage(IsoDirectoryBase<Config>& directory, unsigned index);
69
70 static IsoPage* pageFor(void*);
71
72 unsigned index() const { return m_index; }
73
74 void free(void*);
75
76 // Called after this page is already selected for allocation.
77 FreeList startAllocating();
78
79 // Called after the allocator picks another page to replace this one.
80 void stopAllocating(FreeList freeList);
81
82 IsoDirectoryBase<Config>& directory() { return m_directory; }
83 bool isInUseForAllocation() const { return m_isInUseForAllocation; }
84
85 template<typename Func>
86 void forEachLiveObject(const Func&);
87
88 IsoHeapImpl<Config>& heap();
89
90private:
91 static constexpr unsigned indexOfFirstObject()
92 {
93 return (sizeof(IsoPage) + Config::objectSize - 1) / Config::objectSize;
94 }
95
96 // The possible states of a page are as follows. We mark these states by their corresponding
97 // eligible, empty, and committed bits (respectively).
98 //
99 // 000 - Deallocated. It has no objects and its memory is not paged in.
100 // 111 - Empty.
101 // 101 - Eligible for allocation, meaning that there is at least one free object in the page.
102 // 001 - Full.
103 // 001 - Currently being used for allocation.
104 //
105 // Note that the last two states have identical representation in the directory, which is fine - in
106 // both cases we are basically telling the directory that this page is off limits. But we keep track
107 // of the distinction internally.
108
109 // We manage the bitvector ourselves. This bitvector works in a special way to enable very fast
110 // freeing.
111
112 // This must have a trivial destructor.
113
114 bool m_eligibilityHasBeenNoted { true };
115 bool m_isInUseForAllocation { false };
116 DeferredTrigger<IsoPageTrigger::Eligible> m_eligibilityTrigger;
117 DeferredTrigger<IsoPageTrigger::Empty> m_emptyTrigger;
118
119 IsoDirectoryBase<Config>& m_directory;
120 unsigned m_index { UINT_MAX };
121
122 unsigned m_allocBits[bitsArrayLength(numObjects)];
123 unsigned m_numNonEmptyWords { 0 };
124};
125
126} // namespace bmalloc
127
128