1 //===-- dfsan_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 // This file is a part of DataFlowSanitizer.
10 //
11 // Origin id utils.
12 //===----------------------------------------------------------------------===//
13 
14 #ifndef DFSAN_ORIGIN_H
15 #define DFSAN_ORIGIN_H
16 
17 #include "dfsan_chained_origin_depot.h"
18 #include "dfsan_flags.h"
19 #include "sanitizer_common/sanitizer_stackdepot.h"
20 
21 namespace __dfsan {
22 
23 // Origin handling.
24 //
25 // Origin is a 32-bit identifier that is attached to any taint value in the
26 // program and describes how this memory came to be tainted.
27 //
28 // Chained origin id is like:
29 // zzzz xxxx xxxx xxxx
30 //
31 // Chained origin id describes an event of storing a taint value to
32 // memory. The xxx part is a value of ChainedOriginDepot, which is a mapping of
33 // (stack_id, prev_id) -> id, where
34 //  * stack_id describes the event.
35 //    StackDepot keeps a mapping between those and corresponding stack traces.
36 //  * prev_id is another origin id that describes the earlier part of the
37 //    taint value history. 0 prev_id indicates the start of a chain.
38 // Following a chain of prev_id provides the full recorded history of a taint
39 // value.
40 //
41 // This, effectively, defines a forest where nodes are points in value history
42 // marked with origin ids, and edges are events that are marked with stack_id.
43 //
44 // The "zzzz" bits of chained origin id are used to store the length of the
45 // origin chain.
46 
47 class Origin {
48  public:
isValidId(u32 id)49   static bool isValidId(u32 id) { return id != 0; }
50 
raw_id()51   u32 raw_id() const { return raw_id_; }
52 
isChainedOrigin()53   bool isChainedOrigin() const { return Origin::isValidId(raw_id_); }
54 
getChainedId()55   u32 getChainedId() const {
56     CHECK(Origin::isValidId(raw_id_));
57     return raw_id_ & kChainedIdMask;
58   }
59 
60   // Returns the next origin in the chain and the current stack trace.
61   //
62   // It scans a partition of StackDepot linearly, and is used only by origin
63   // tracking report.
getNextChainedOrigin(StackTrace * stack)64   Origin getNextChainedOrigin(StackTrace *stack) const {
65     CHECK(Origin::isValidId(raw_id_));
66     u32 prev_id;
67     u32 stack_id = GetChainedOriginDepot()->Get(getChainedId(), &prev_id);
68     if (stack)
69       *stack = StackDepotGet(stack_id);
70     return Origin(prev_id);
71   }
72 
CreateChainedOrigin(Origin prev,StackTrace * stack)73   static Origin CreateChainedOrigin(Origin prev, StackTrace *stack) {
74     int depth = prev.isChainedOrigin() ? prev.depth() : -1;
75     // depth is the length of the chain minus 1.
76     // origin_history_size of 0 means unlimited depth.
77     if (flags().origin_history_size > 0) {
78       ++depth;
79       if (depth >= flags().origin_history_size || depth > kMaxDepth)
80         return prev;
81     }
82 
83     StackDepotHandle h = StackDepotPut_WithHandle(*stack);
84     if (!h.valid())
85       return prev;
86 
87     if (flags().origin_history_per_stack_limit > 0) {
88       int use_count = h.use_count();
89       if (use_count > flags().origin_history_per_stack_limit)
90         return prev;
91     }
92 
93     u32 chained_id;
94     bool inserted =
95         GetChainedOriginDepot()->Put(h.id(), prev.raw_id(), &chained_id);
96     CHECK((chained_id & kChainedIdMask) == chained_id);
97 
98     if (inserted && flags().origin_history_per_stack_limit > 0)
99       h.inc_use_count_unsafe();
100 
101     return Origin((depth << kDepthShift) | chained_id);
102   }
103 
FromRawId(u32 id)104   static Origin FromRawId(u32 id) { return Origin(id); }
105 
106  private:
107   static const int kDepthBits = 4;
108   static const int kDepthShift = 32 - kDepthBits;
109 
110   static const u32 kChainedIdMask = ((u32)-1) >> kDepthBits;
111 
112   u32 raw_id_;
113 
Origin(u32 raw_id)114   explicit Origin(u32 raw_id) : raw_id_(raw_id) {}
115 
depth()116   int depth() const {
117     CHECK(isChainedOrigin());
118     return (raw_id_ >> kDepthShift) & ((1 << kDepthBits) - 1);
119   }
120 
121  public:
122   static const int kMaxDepth = (1 << kDepthBits) - 1;
123 };
124 
125 }  // namespace __dfsan
126 
127 #endif  // DFSAN_ORIGIN_H
128