1/*
2 * Copyright (C) 2020 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 "Mutex.h"
29#include "ObjectType.h"
30#include "Sizes.h"
31
32namespace bmalloc {
33
34class Chunk;
35
36// Querying ObjectType for Chunk without locking.
37class ObjectTypeTable {
38public:
39 ObjectTypeTable();
40
41 static_assert(BOS_EFFECTIVE_ADDRESS_WIDTH != 64);
42 static constexpr unsigned shiftAmount = 20;
43 static constexpr uintptr_t addressMask = (1ULL << BOS_EFFECTIVE_ADDRESS_WIDTH) - 1;
44 static_assert((1ULL << shiftAmount) == chunkSize);
45 static_assert((BOS_EFFECTIVE_ADDRESS_WIDTH - shiftAmount) <= 32);
46
47 class Bits;
48
49 ObjectType get(Chunk*);
50 void set(UniqueLockHolder&, Chunk*, ObjectType);
51
52private:
53 static unsigned convertToIndex(Chunk* chunk)
54 {
55 uintptr_t address = reinterpret_cast<uintptr_t>(chunk);
56 BASSERT(!(address & (~chunkMask)));
57 return static_cast<unsigned>((address & addressMask) >> shiftAmount);
58 }
59
60 Bits* m_bits;
61};
62
63class ObjectTypeTable::Bits {
64public:
65 using WordType = unsigned;
66 static constexpr unsigned bitCountPerWord = sizeof(WordType) * 8;
67 static constexpr WordType one = 1;
68 constexpr Bits(Bits* previous, unsigned begin, unsigned end)
69 : m_previous(previous)
70 , m_begin(begin)
71 , m_end(end)
72 {
73 }
74
75 bool get(unsigned index);
76 void set(unsigned index, bool);
77
78 Bits* previous() const { return m_previous; }
79 unsigned begin() const { return m_begin; }
80 unsigned end() const { return m_end; }
81
82private:
83 const WordType* words() const { return const_cast<Bits*>(this)->words(); }
84 WordType* words() { return reinterpret_cast<WordType*>(reinterpret_cast<uintptr_t>(this) + sizeof(Bits)); }
85
86 Bits* m_previous { nullptr }; // Keeping the previous Bits* just to suppress Leaks warnings.
87 unsigned m_begin { 0 };
88 unsigned m_end { 0 };
89};
90static_assert(!(sizeof(ObjectTypeTable::Bits) % sizeof(ObjectTypeTable::Bits::WordType)));
91
92extern BEXPORT ObjectTypeTable::Bits sentinelBits;
93
94inline ObjectTypeTable::ObjectTypeTable()
95 : m_bits(&sentinelBits)
96{
97}
98
99inline ObjectType ObjectTypeTable::get(Chunk* chunk)
100{
101 Bits* bits = m_bits;
102 unsigned index = convertToIndex(chunk);
103 BASSERT(bits);
104 if (bits->begin() <= index && index < bits->end())
105 return static_cast<ObjectType>(bits->get(index));
106 return { };
107}
108
109inline bool ObjectTypeTable::Bits::get(unsigned index)
110{
111 unsigned n = index - begin();
112 return words()[n / bitCountPerWord] & (one << (n % bitCountPerWord));
113}
114
115inline void ObjectTypeTable::Bits::set(unsigned index, bool value)
116{
117 unsigned n = index - begin();
118 if (value)
119 words()[n / bitCountPerWord] |= (one << (n % bitCountPerWord));
120 else
121 words()[n / bitCountPerWord] &= ~(one << (n % bitCountPerWord));
122}
123
124} // namespace bmalloc