1// Copyright (c) 2013, the Dart project authors. Please see the AUTHORS file
2// for details. All rights reserved. Use of this source code is governed by a
3// BSD-style license that can be found in the LICENSE file.
4
5#ifndef RUNTIME_VM_OBJECT_ID_RING_H_
6#define RUNTIME_VM_OBJECT_ID_RING_H_
7
8#include "platform/globals.h"
9#include "vm/tagged_pointer.h"
10
11namespace dart {
12
13// Forward declarations.
14class ObjectPointerVisitor;
15class JSONStream;
16
17// A ring buffer of object pointers that have been given an id. An object
18// may be pointed to by multiple ids. Objects contained in the ring will
19// be preserved across scavenges but not old space collections.
20// When the ring buffer wraps around older objects will be replaced and their
21// ids will be invalidated.
22class ObjectIdRing {
23 public:
24 enum LookupResult {
25 kValid = 0,
26 kInvalid, // Malformed ring id (used in service.cc).
27 kCollected, // Entry was reclaimed due to a full GC (entries are weak).
28 kExpired, // Entry was evicted during an insertion into a full ring.
29 };
30
31 enum IdPolicy {
32 kAllocateId, // Always allocate a new object id.
33 kReuseId, // If the object is already in the ring, reuse id.
34 // Otherwise allocate a new object id.
35 kNumIdPolicy,
36 };
37
38 static const int32_t kMaxId = 0x3FFFFFFF;
39 static const int32_t kInvalidId = -1;
40 static const int32_t kDefaultCapacity = 8192;
41
42 ObjectIdRing();
43 ~ObjectIdRing();
44
45 // Adds the argument to the ring and returns its id. Note we do not allow
46 // adding Object::null().
47 int32_t GetIdForObject(ObjectPtr raw_obj, IdPolicy policy = kAllocateId);
48
49 // Returns Object::null() when the result is not kValid.
50 ObjectPtr GetObjectForId(int32_t id, LookupResult* kind);
51
52 void VisitPointers(ObjectPointerVisitor* visitor);
53
54 void PrintJSON(JSONStream* js);
55
56 private:
57 friend class ObjectIdRingTestHelper;
58
59 void SetCapacityAndMaxSerial(int32_t capacity, int32_t max_serial);
60 int32_t FindExistingIdForObject(ObjectPtr raw_obj);
61
62 ObjectPtr* table_;
63 int32_t max_serial_;
64 int32_t capacity_;
65 int32_t serial_num_;
66 bool wrapped_;
67
68 ObjectPtr* table() { return table_; }
69 int32_t table_size() { return capacity_; }
70
71 int32_t NextSerial();
72 int32_t AllocateNewId(ObjectPtr object);
73 int32_t IndexOfId(int32_t id);
74 int32_t IdOfIndex(int32_t index);
75 bool IsValidContiguous(int32_t id);
76 bool IsValidId(int32_t id);
77
78 DISALLOW_COPY_AND_ASSIGN(ObjectIdRing);
79};
80
81} // namespace dart
82
83#endif // RUNTIME_VM_OBJECT_ID_RING_H_
84