tor  0.4.1.1-alpha-dev
di_ops.c
Go to the documentation of this file.
1 /* Copyright (c) 2011-2019, The Tor Project, Inc. */
2 /* See LICENSE for licensing information */
3 
9 #include "orconfig.h"
10 #include "lib/ctime/di_ops.h"
11 #include "lib/err/torerr.h"
12 #include "lib/malloc/malloc.h"
13 
14 #include <string.h>
15 
30 int
31 tor_memcmp(const void *a, const void *b, size_t len)
32 {
33 #ifdef HAVE_TIMINGSAFE_MEMCMP
34  return timingsafe_memcmp(a, b, len);
35 #else
36  const uint8_t *x = a;
37  const uint8_t *y = b;
38  size_t i = len;
39  int retval = 0;
40 
41  /* This loop goes from the end of the arrays to the start. At the
42  * start of every iteration, before we decrement i, we have set
43  * "retval" equal to the result of memcmp(a+i,b+i,len-i). During the
44  * loop, we update retval by leaving it unchanged if x[i]==y[i] and
45  * setting it to x[i]-y[i] if x[i]!= y[i].
46  *
47  * The following assumes we are on a system with two's-complement
48  * arithmetic. We check for this at configure-time with the check
49  * that sets USING_TWOS_COMPLEMENT. If we aren't two's complement, then
50  * torint.h will stop compilation with an error.
51  */
52  while (i--) {
53  int v1 = x[i];
54  int v2 = y[i];
55  int equal_p = v1 ^ v2;
56 
57  /* The following sets bits 8 and above of equal_p to 'equal_p ==
58  * 0', and thus to v1 == v2. (To see this, note that if v1 ==
59  * v2, then v1^v2 == equal_p == 0, so equal_p-1 == -1, which is the
60  * same as ~0 on a two's-complement machine. Then note that if
61  * v1 != v2, then 0 < v1 ^ v2 < 256, so 0 <= equal_p - 1 < 255.)
62  */
63  --equal_p;
64 
65  equal_p >>= 8;
66  /* Thanks to (sign-preserving) arithmetic shift, equal_p is now
67  * equal to -(v1 == v2), which is exactly what we need below.
68  * (Since we're assuming two's-complement arithmetic, -1 is the
69  * same as ~0 (all bits set).)
70  *
71  * (The result of an arithmetic shift on a negative value is
72  * actually implementation-defined in standard C. So how do we
73  * get away with assuming it? Easy. We check.) */
74 #if ((-60 >> 8) != -1)
75 #error "According to cpp, right-shift doesn't perform sign-extension."
76 #endif
77 #ifndef RSHIFT_DOES_SIGN_EXTEND
78 #error "According to configure, right-shift doesn't perform sign-extension."
79 #endif
80 
81  /* If v1 == v2, equal_p is ~0, so this will leave retval
82  * unchanged; otherwise, equal_p is 0, so this will zero it. */
83  retval &= equal_p;
84 
85  /* If v1 == v2, then this adds 0, and leaves retval unchanged.
86  * Otherwise, we just zeroed retval, so this sets it to v1 - v2. */
87  retval += (v1 - v2);
88 
89  /* There. Now retval is equal to its previous value if v1 == v2, and
90  * equal to v1 - v2 if v1 != v2. */
91  }
92 
93  return retval;
94 #endif /* defined(HAVE_TIMINGSAFE_MEMCMP) */
95 }
96 
106 int
107 tor_memeq(const void *a, const void *b, size_t sz)
108 {
109  /* Treat a and b as byte ranges. */
110  const uint8_t *ba = a, *bb = b;
111  uint32_t any_difference = 0;
112  while (sz--) {
113  /* Set byte_diff to all of those bits that are different in *ba and *bb,
114  * and advance both ba and bb. */
115  const uint8_t byte_diff = *ba++ ^ *bb++;
116 
117  /* Set bits in any_difference if they are set in byte_diff. */
118  any_difference |= byte_diff;
119  }
120 
121  /* Now any_difference is 0 if there are no bits different between
122  * a and b, and is nonzero if there are bits different between a
123  * and b. Now for paranoia's sake, let's convert it to 0 or 1.
124  *
125  * (If we say "!any_difference", the compiler might get smart enough
126  * to optimize-out our data-independence stuff above.)
127  *
128  * To unpack:
129  *
130  * If any_difference == 0:
131  * any_difference - 1 == ~0
132  * (any_difference - 1) >> 8 == 0x00ffffff
133  * 1 & ((any_difference - 1) >> 8) == 1
134  *
135  * If any_difference != 0:
136  * 0 < any_difference < 256, so
137  * 0 <= any_difference - 1 < 255
138  * (any_difference - 1) >> 8 == 0
139  * 1 & ((any_difference - 1) >> 8) == 0
140  */
141 
142  /*coverity[overflow]*/
143  return 1 & ((any_difference - 1) >> 8);
144 }
145 
146 /* Implement di_digest256_map_t as a linked list of entries. */
148  struct di_digest256_map_t *next;
149  uint8_t key[32];
150  void *val;
151 };
152 
155 void
156 dimap_free_(di_digest256_map_t *map, dimap_free_fn free_fn)
157 {
158  while (map) {
159  di_digest256_map_t *victim = map;
160  map = map->next;
161  if (free_fn)
162  free_fn(victim->val);
163  tor_free(victim);
164  }
165 }
166 
172 void
174  const uint8_t *key, void *val)
175 {
176  di_digest256_map_t *new_ent;
177  {
178  void *old_val = dimap_search(*map, key, NULL);
179  raw_assert(! old_val);
180  raw_assert(val);
181  }
182  new_ent = tor_malloc_zero(sizeof(di_digest256_map_t));
183  new_ent->next = *map;
184  memcpy(new_ent->key, key, 32);
185  new_ent->val = val;
186  *map = new_ent;
187 }
188 
196 void *
197 dimap_search(const di_digest256_map_t *map, const uint8_t *key,
198  void *dflt_val)
199 {
200  uintptr_t result = (uintptr_t)dflt_val;
201 
202  while (map) {
203  uintptr_t r = (uintptr_t) tor_memeq(map->key, key, 32);
204  r -= 1; /* Now r is (uintptr_t)-1 if memeq returned false, and
205  * 0 if memeq returned true. */
206 
207  result &= r;
208  result |= ((uintptr_t)(map->val)) & ~r;
209 
210  map = map->next;
211  }
212 
213  return (void *)result;
214 }
215 
220 int
221 safe_mem_is_zero(const void *mem, size_t sz)
222 {
223  uint32_t total = 0;
224  const uint8_t *ptr = mem;
225 
226  while (sz--) {
227  total |= *ptr++;
228  }
229 
230  /*coverity[overflow]*/
231  return 1 & ((total - 1) >> 8);
232 }
233 
236 #if SIZEOF_VOID_P == 8
237 #define gt_i64_timei(a,b) ((a) > (b))
238 #else
239 static inline int
240 gt_i64_timei(uint64_t a, uint64_t b)
241 {
242  int64_t diff = (int64_t) (b - a);
243  int res = diff >> 63;
244  return res & 1;
245 }
246 #endif /* SIZEOF_VOID_P == 8 */
247 
255 int
256 select_array_member_cumulative_timei(const uint64_t *entries, int n_entries,
257  uint64_t total, uint64_t rand_val)
258 {
259  int i, i_chosen=-1, n_chosen=0;
260  uint64_t total_so_far = 0;
261 
262  for (i = 0; i < n_entries; ++i) {
263  total_so_far += entries[i];
264  if (gt_i64_timei(total_so_far, rand_val)) {
265  i_chosen = i;
266  n_chosen++;
267  /* Set rand_val to INT64_MAX rather than stopping the loop. This way,
268  * the time we spend in the loop does not leak which element we chose. */
269  rand_val = INT64_MAX;
270  }
271  }
272  raw_assert(total_so_far == total);
273  raw_assert(n_chosen == 1);
274  raw_assert(i_chosen >= 0);
275  raw_assert(i_chosen < n_entries);
276 
277  return i_chosen;
278 }
Headers for di_ops.c.
void * dimap_search(const di_digest256_map_t *map, const uint8_t *key, void *dflt_val)
Definition: di_ops.c:197
#define tor_free(p)
Definition: malloc.h:52
void dimap_add_entry(di_digest256_map_t **map, const uint8_t *key, void *val)
Definition: di_ops.c:173
Headers for util_malloc.c.
int tor_memcmp(const void *a, const void *b, size_t len)
Definition: di_ops.c:31
int tor_memeq(const void *a, const void *b, size_t sz)
Definition: di_ops.c:107
int select_array_member_cumulative_timei(const uint64_t *entries, int n_entries, uint64_t total, uint64_t rand_val)
Definition: di_ops.c:256
static int gt_i64_timei(uint64_t a, uint64_t b)
Definition: di_ops.c:240
Headers for torerr.c.
int safe_mem_is_zero(const void *mem, size_t sz)
Definition: di_ops.c:221
void dimap_free_(di_digest256_map_t *map, dimap_free_fn free_fn)
Definition: di_ops.c:156