blob: dd23d15abbc3fa025d0183c14526ba27eb4570ca [file] [log] [blame]
Carl Shapiro69759ea2011-07-21 18:13:35 -07001// Copyright (C) 2008 The Android Open Source Project
2//
3// Licensed under the Apache License, Version 2.0 (the "License");
4// you may not use this file except in compliance with the License.
5// You may obtain a copy of the License at
6//
7// http://www.apache.org/licenses/LICENSE-2.0
8//
9// Unless required by applicable law or agreed to in writing, software
10// distributed under the License is distributed on an "AS IS" BASIS,
11// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12// See the License for the specific language governing permissions and
13// limitations under the License.
14
15#ifndef ART_SRC_OBJECT_BITMAP_H_
16#define ART_SRC_OBJECT_BITMAP_H_
17
18#include <limits.h>
19#include <stdint.h>
20
Elliott Hughes90a33692011-08-30 13:27:07 -070021#include "UniquePtr.h"
Brian Carlstrom578bbdc2011-07-21 14:07:47 -070022#include "globals.h"
23#include "logging.h"
Brian Carlstromdb4d5402011-08-09 12:18:28 -070024#include "mem_map.h"
Carl Shapiro69759ea2011-07-21 18:13:35 -070025
26namespace art {
27
28class Object;
29
30// <offset> is the difference from .base to a pointer address.
31// <index> is the index of .bits that contains the bit representing
32// <offset>.
33#define HB_OFFSET_TO_INDEX(offset_) \
34 ((offset_) / kAlignment / kBitsPerWord)
35#define HB_INDEX_TO_OFFSET(index_) \
36 ((index_) * kAlignment * kBitsPerWord)
37
38#define HB_OFFSET_TO_BYTE_INDEX(offset_) \
39 (HB_OFFSET_TO_INDEX(offset_) * sizeof(*((HeapBitmap *)0)->words_))
40
41// Pack the bits in backwards so they come out in address order
42// when using CLZ.
43#define HB_OFFSET_TO_MASK(offset_) \
44 (1 << \
45 (31-(((uintptr_t)(offset_) / kAlignment) % kBitsPerWord)))
46
47class HeapBitmap {
48 public:
49 static const size_t kAlignment = 8;
50
Brian Carlstrom4873d462011-08-21 15:23:39 -070051 typedef void Callback(Object* obj, void *arg);
Carl Shapiro69759ea2011-07-21 18:13:35 -070052
Brian Carlstrom4873d462011-08-21 15:23:39 -070053 typedef void ScanCallback(Object* obj, void *finger, void *arg);
Carl Shapiro69759ea2011-07-21 18:13:35 -070054
55 typedef void SweepCallback(size_t numPtrs, void **ptrs, void *arg);
56
57 static HeapBitmap* Create(byte* base, size_t length);
58
59 ~HeapBitmap();
60
61 void Set(const Object* obj) {
62 Modify(obj, true);
63 }
64
65 void Clear(const Object* obj) {
66 Modify(obj, false);
67 }
68
69 void Clear();
70
71 bool Test(const Object* obj) {
72 CHECK(HasAddress(obj));
73 CHECK(words_ != NULL);
74 CHECK_GE((uintptr_t)obj, base_);
75 if ((uintptr_t)obj <= max_) {
76 const uintptr_t offset = (uintptr_t)obj - base_;
77 unsigned long word = words_[HB_OFFSET_TO_INDEX(offset)];
78 return (word & HB_OFFSET_TO_MASK(offset)) != 0;
79 } else {
80 return false;
81 }
82 }
83
84 bool HasAddress(const void* addr) const;
85
86 void Walk(Callback* callback, void* arg);
87
Brian Carlstrom1f870082011-08-23 16:02:11 -070088 void ScanWalk(uintptr_t base, ScanCallback* thunk, void* arg);
Carl Shapiro69759ea2011-07-21 18:13:35 -070089
90 static void SweepWalk(const HeapBitmap& live,
91 const HeapBitmap& mark,
92 uintptr_t base, uintptr_t max,
93 SweepCallback* thunk, void* arg);
94
95 private:
96 HeapBitmap(const void* base, size_t length)
97 : words_(NULL),
98 num_bytes_(length),
99 base_(reinterpret_cast<uintptr_t>(base)) {
100 };
101
102 void Modify(const Object* obj, bool do_set) {
103 uintptr_t addr = reinterpret_cast<uintptr_t>(obj);
104 CHECK_GE(addr, base_);
105 const uintptr_t offset = addr - base_;
106 const size_t index = HB_OFFSET_TO_INDEX(offset);
107 const unsigned long mask = HB_OFFSET_TO_MASK(offset);
108 CHECK_LT(index, num_bytes_ / kWordSize);
109 if (do_set) {
110 if (addr > max_) {
111 max_ = addr;
112 }
113 words_[index] |= mask;
114 } else {
115 words_[index] &= ~mask;
116 }
117 }
118
119 bool Init(const byte* base, size_t length);
120
Elliott Hughes90a33692011-08-30 13:27:07 -0700121 UniquePtr<MemMap> mem_map_;
Brian Carlstromdb4d5402011-08-09 12:18:28 -0700122
123 word* words_;
Carl Shapiro69759ea2011-07-21 18:13:35 -0700124
125 size_t num_bytes_;
126
127 // The base address, which corresponds to the word containing the
128 // first bit in the bitmap.
129 uintptr_t base_;
130
131 // The highest pointer value ever returned by an allocation from
132 // this heap. I.e., the highest address that may correspond to a
Brian Carlstrom1f870082011-08-23 16:02:11 -0700133 // set bit. If there are no bits set, (max_ < base_).
Carl Shapiro69759ea2011-07-21 18:13:35 -0700134 uintptr_t max_;
135
136 const char* name_;
137};
138
139} // namespace art
140
141#endif // ART_SRC_OBJECT_BITMAP_H_