1//===-- msan_origin.h ----------------------------------*- C++ -*-===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8//
9// Origin id utils.
10//===----------------------------------------------------------------------===//
11#ifndef MSAN_ORIGIN_H
12#define MSAN_ORIGIN_H
13
14#include "sanitizer_common/sanitizer_stackdepot.h"
15#include "msan_chained_origin_depot.h"
16
17namespace __msan {
18
19// Origin handling.
20//
21// Origin is a 32-bit identifier that is attached to any uninitialized value in
22// the program and describes, more or less exactly, how this memory came to be
23// uninitialized.
24//
25// There are 3 kinds of origin ids:
26// 1xxx xxxx xxxx xxxx   heap origin id
27// 0000 xxxx xxxx xxxx   stack origin id
28// 0zzz xxxx xxxx xxxx   chained origin id
29//
30// Heap origin id describes a heap memory allocation and contains (in the xxx
31// part) a value of StackDepot.
32//
33// Stack origin id describes a stack memory allocation and contains (in the xxx
34// part) an index into StackOriginDescr and StackOriginPC. We don't store a
35// stack trace for such origins for performance reasons.
36//
37// Chained origin id describes an event of storing an uninitialized value to
38// memory. The xxx part is a value of ChainedOriginDepot, which is a mapping of
39// (stack_id, prev_id) -> id, where
40//  * stack_id describes the event.
41//    StackDepot keeps a mapping between those and corresponding stack traces.
42//  * prev_id is another origin id that describes the earlier part of the
43//    uninitialized value history.
44// Following a chain of prev_id provides the full recorded history of an
45// uninitialized value.
46//
47// This, effectively, defines a tree (or 2 trees, see below) where nodes are
48// points in value history marked with origin ids, and edges are events that are
49// marked with stack_id.
50//
51// The "zzz" bits of chained origin id are used to store the length (or depth)
52// of the origin chain.
53
54class Origin {
55 public:
56  static bool isValidId(u32 id) { return id != 0 && id != (u32)-1; }
57
58  u32 raw_id() const { return raw_id_; }
59  bool isHeapOrigin() const {
60    // 0xxx xxxx xxxx xxxx
61    return raw_id_ >> kHeapShift == 0;
62  }
63  bool isStackOrigin() const {
64    // 1000 xxxx xxxx xxxx
65    return (raw_id_ >> kDepthShift) == (1 << kDepthBits);
66  }
67  bool isChainedOrigin() const {
68    // 1zzz xxxx xxxx xxxx, zzz != 000
69    return (raw_id_ >> kDepthShift) > (1 << kDepthBits);
70  }
71  u32 getChainedId() const {
72    CHECK(isChainedOrigin());
73    return raw_id_ & kChainedIdMask;
74  }
75  u32 getStackId() const {
76    CHECK(isStackOrigin());
77    return raw_id_ & kChainedIdMask;
78  }
79  u32 getHeapId() const {
80    CHECK(isHeapOrigin());
81    return raw_id_ & kHeapIdMask;
82  }
83
84  // Returns the next origin in the chain and the current stack trace.
85  Origin getNextChainedOrigin(StackTrace *stack) const {
86    CHECK(isChainedOrigin());
87    u32 prev_id;
88    u32 stack_id = ChainedOriginDepotGet(getChainedId(), &prev_id);
89    if (stack) *stack = StackDepotGet(stack_id);
90    return Origin(prev_id);
91  }
92
93  StackTrace getStackTraceForHeapOrigin() const {
94    return StackDepotGet(getHeapId());
95  }
96
97  static Origin CreateStackOrigin(u32 id) {
98    CHECK((id & kStackIdMask) == id);
99    return Origin((1 << kHeapShift) | id);
100  }
101
102  static Origin CreateHeapOrigin(StackTrace *stack) {
103    u32 stack_id = StackDepotPut(*stack);
104    CHECK(stack_id);
105    CHECK((stack_id & kHeapIdMask) == stack_id);
106    return Origin(stack_id);
107  }
108
109  static Origin CreateChainedOrigin(Origin prev, StackTrace *stack) {
110    int depth = prev.isChainedOrigin() ? prev.depth() : 0;
111    // depth is the length of the chain minus 1.
112    // origin_history_size of 0 means unlimited depth.
113    if (flags()->origin_history_size > 0) {
114      if (depth + 1 >= flags()->origin_history_size) {
115        return prev;
116      } else {
117        ++depth;
118        CHECK(depth < (1 << kDepthBits));
119      }
120    }
121
122    StackDepotHandle h = StackDepotPut_WithHandle(*stack);
123    if (!h.valid()) return prev;
124
125    if (flags()->origin_history_per_stack_limit > 0) {
126      int use_count = h.use_count();
127      if (use_count > flags()->origin_history_per_stack_limit) return prev;
128    }
129
130    u32 chained_id;
131    bool inserted = ChainedOriginDepotPut(h.id(), prev.raw_id(), &chained_id);
132    CHECK((chained_id & kChainedIdMask) == chained_id);
133
134    if (inserted && flags()->origin_history_per_stack_limit > 0)
135      h.inc_use_count_unsafe();
136
137    return Origin((1 << kHeapShift) | (depth << kDepthShift) | chained_id);
138  }
139
140  static Origin FromRawId(u32 id) {
141    return Origin(id);
142  }
143
144 private:
145  static const int kDepthBits = 3;
146  static const int kDepthShift = 32 - kDepthBits - 1;
147
148  static const int kHeapShift = 31;
149  static const u32 kChainedIdMask = ((u32)-1) >> (32 - kDepthShift);
150  static const u32 kStackIdMask = ((u32)-1) >> (32 - kDepthShift);
151  static const u32 kHeapIdMask = ((u32)-1) >> (32 - kHeapShift);
152
153  u32 raw_id_;
154
155  explicit Origin(u32 raw_id) : raw_id_(raw_id) {}
156
157  int depth() const {
158    CHECK(isChainedOrigin());
159    return (raw_id_ >> kDepthShift) & ((1 << kDepthBits) - 1);
160  }
161
162 public:
163  static const int kMaxDepth = (1 << kDepthBits) - 1;
164};
165
166}  // namespace __msan
167
168#endif  // MSAN_ORIGIN_H
169