| 1 |
// Copyright (c) Meta Platforms, Inc. and affiliates. |
| 2 |
// SPDX-License-Identifier: LGPL-2.1-or-later |
| 3 |
|
| 4 |
#include <assert.h> |
| 5 |
#include <byteswap.h> |
| 6 |
#include <endian.h> |
| 7 |
#include <errno.h> |
| 8 |
#ifdef WITH_PCRE2 |
| 9 |
#define PCRE2_CODE_UNIT_WIDTH 8 |
| 10 |
#include <pcre2.h> |
| 11 |
#endif |
| 12 |
#include <stdlib.h> |
| 13 |
#include <string.h> |
| 14 |
#include <unistd.h> |
| 15 |
|
| 16 |
#include "bitops.h" |
| 17 |
#include "cleanup.h" |
| 18 |
#include "error.h" |
| 19 |
#include "helpers.h" |
| 20 |
#include "memory_reader.h" |
| 21 |
#include "minmax.h" |
| 22 |
#include "program.h" |
| 23 |
#include "string_builder.h" |
| 24 |
#include "vector.h" |
| 25 |
|
| 26 |
#ifdef WITH_PCRE2 |
| 27 |
#define _cleanup_pcre2_code_ _cleanup_(pcre2_code_freep) |
| 28 |
static inline void pcre2_code_freep(pcre2_code **codep) |
| 29 |
{ |
| 30 |
pcre2_code_free(*codep); |
| 31 |
} |
| 32 |
|
| 33 |
#define _cleanup_pcre2_match_data_ _cleanup_(pcre2_match_data_freep) |
| 34 |
static inline void pcre2_match_data_freep(pcre2_match_data **mdp) |
| 35 |
{ |
| 36 |
pcre2_match_data_free(*mdp); |
| 37 |
} |
| 38 |
|
| 39 |
__attribute__((__returns_nonnull__)) |
| 40 |
static struct drgn_error *drgn_error_pcre2(int errorcode, PCRE2_SIZE *offset) |
| 41 |
{ |
| 42 |
PCRE2_UCHAR buf[128]; |
| 43 |
int len = pcre2_get_error_message(errorcode, buf, sizeof(buf)); |
| 44 |
if (len == PCRE2_ERROR_BADDATA) { |
| 45 |
return drgn_error_create(DRGN_ERROR_OTHER, |
| 46 |
"unknown pcre2 error"); |
| 47 |
} |
| 48 |
if (offset) { |
| 49 |
return drgn_error_format(DRGN_ERROR_OTHER, |
| 50 |
"pcre2 error at offset %zu: %s", |
| 51 |
(size_t)*offset, (char *)buf); |
| 52 |
} else { |
| 53 |
return drgn_error_format(DRGN_ERROR_OTHER, "pcre2 error: %s", |
| 54 |
(char *)buf); |
| 55 |
} |
| 56 |
} |
| 57 |
|
| 58 |
// pcre2_next_match() was added in PCRE2 10.47. For older versions, use our own |
| 59 |
// copy based on PCRE2's. Doing it ourselves requires a bunch of extra arguments |
| 60 |
// that are usually saved in the pcre2_match_data but we can't access. |
| 61 |
#if PCRE2_MAJOR > 10 || (PCRE2_MAJOR == 10 && PCRE2_MINOR >= 47) |
| 62 |
static int drgn_pcre2_next_match(pcre2_match_data *match_data, bool utf, |
| 63 |
const unsigned char *subject, |
| 64 |
PCRE2_SIZE subject_length, |
| 65 |
PCRE2_SIZE start_offset, PCRE2_SIZE *ovector, |
| 66 |
PCRE2_SIZE *pstart_offset, uint32_t *poptions) |
| 67 |
{ |
| 68 |
return pcre2_next_match(match_data, pstart_offset, poptions); |
| 69 |
} |
| 70 |
#else |
| 71 |
static int drgn_pcre2_next_match(pcre2_match_data *match_data, bool utf, |
| 72 |
const unsigned char *subject, |
| 73 |
PCRE2_SIZE subject_length, |
| 74 |
PCRE2_SIZE start_offset, PCRE2_SIZE *ovector, |
| 75 |
PCRE2_SIZE *pstart_offset, uint32_t *poptions) |
| 76 |
{ |
| 77 |
if (ovector[0] != start_offset && ovector[1] == start_offset) { |
| 78 |
if (start_offset >= subject_length) |
| 79 |
return 0; |
| 80 |
|
| 81 |
PCRE2_SIZE offset = ovector[1] + 1; |
| 82 |
if (utf) { |
| 83 |
for (; offset < subject_length; offset++) { |
| 84 |
if ((subject[offset] & 0xc0) != 0x80) |
| 85 |
break; |
| 86 |
} |
| 87 |
} |
| 88 |
*pstart_offset = offset; |
| 89 |
*poptions = 0; |
| 90 |
return 1; |
| 91 |
} |
| 92 |
|
| 93 |
if (ovector[0] == ovector[1]) { |
| 94 |
if (ovector[0] >= subject_length) |
| 95 |
return 0; |
| 96 |
*pstart_offset = ovector[1]; |
| 97 |
*poptions = PCRE2_NOTEMPTY_ATSTART; |
| 98 |
return 1; |
| 99 |
} |
| 100 |
|
| 101 |
*pstart_offset = ovector[1]; |
| 102 |
*poptions = 0; |
| 103 |
return 1; |
| 104 |
} |
| 105 |
#endif |
| 106 |
#endif |
| 107 |
|
| 108 |
/** Memory segment in a @ref drgn_memory_reader. */ |
| 109 |
struct drgn_memory_segment { |
| 110 |
struct binary_tree_node node; |
| 111 |
/** Address range of the segment in memory (inclusive). */ |
| 112 |
uint64_t min_address, max_address; |
| 113 |
/** |
| 114 |
* The address of the segment when it was added, before any truncations. |
| 115 |
* |
| 116 |
* This is always less than or equal to @ref |
| 117 |
* drgn_memory_segment::min_address. |
| 118 |
*/ |
| 119 |
uint64_t orig_min_address; |
| 120 |
/** Read callback. */ |
| 121 |
drgn_memory_read_fn read_fn; |
| 122 |
/** Argument to pass to @ref drgn_memory_segment::read_fn. */ |
| 123 |
void *arg; |
| 124 |
}; |
| 125 |
|
| 126 |
static inline uint64_t |
| 127 |
drgn_memory_segment_to_key(const struct drgn_memory_segment *entry) |
| 128 |
{ |
| 129 |
return entry->min_address; |
| 130 |
} |
| 131 |
|
| 132 |
DEFINE_BINARY_SEARCH_TREE_FUNCTIONS(drgn_memory_segment_tree, node, |
| 133 |
drgn_memory_segment_to_key, |
| 134 |
binary_search_tree_scalar_cmp, splay); |
| 135 |
|
| 136 |
void drgn_memory_reader_init(struct drgn_memory_reader *reader) |
| 137 |
{ |
| 138 |
drgn_memory_segment_tree_init(&reader->virtual_segments); |
| 139 |
drgn_memory_segment_tree_init(&reader->physical_segments); |
| 140 |
} |
| 141 |
|
| 142 |
static void free_memory_segment_tree(struct drgn_memory_segment_tree *tree) |
| 143 |
{ |
| 144 |
struct drgn_memory_segment_tree_iterator it; |
| 145 |
|
| 146 |
it = drgn_memory_segment_tree_first_post_order(tree); |
| 147 |
while (it.entry) { |
| 148 |
struct drgn_memory_segment *entry = it.entry; |
| 149 |
|
| 150 |
it = drgn_memory_segment_tree_next_post_order(it); |
| 151 |
free(entry); |
| 152 |
} |
| 153 |
} |
| 154 |
|
| 155 |
void drgn_memory_reader_deinit(struct drgn_memory_reader *reader) |
| 156 |
{ |
| 157 |
free_memory_segment_tree(&reader->physical_segments); |
| 158 |
free_memory_segment_tree(&reader->virtual_segments); |
| 159 |
} |
| 160 |
|
| 161 |
void drgn_memory_reader_clear(struct drgn_memory_reader *reader) |
| 162 |
{ |
| 163 |
drgn_memory_reader_deinit(reader); |
| 164 |
drgn_memory_reader_init(reader); |
| 165 |
} |
| 166 |
|
| 167 |
void drgn_memory_reader_clear_virtual(struct drgn_memory_reader *reader) |
| 168 |
{ |
| 169 |
free_memory_segment_tree(&reader->virtual_segments); |
| 170 |
drgn_memory_segment_tree_init(&reader->virtual_segments); |
| 171 |
} |
| 172 |
|
| 173 |
bool drgn_memory_reader_empty(struct drgn_memory_reader *reader) |
| 174 |
{ |
| 175 |
return (drgn_memory_segment_tree_empty(&reader->virtual_segments) && |
| 176 |
drgn_memory_segment_tree_empty(&reader->physical_segments)); |
| 177 |
} |
| 178 |
|
| 179 |
struct drgn_error * |
| 180 |
drgn_memory_reader_add_segment(struct drgn_memory_reader *reader, |
| 181 |
uint64_t min_address, uint64_t max_address, |
| 182 |
drgn_memory_read_fn read_fn, void *arg, |
| 183 |
bool physical) |
| 184 |
{ |
| 185 |
assert(min_address <= max_address); |
| 186 |
|
| 187 |
struct drgn_memory_segment_tree *tree = (physical ? |
| 188 |
&reader->physical_segments : |
| 189 |
&reader->virtual_segments); |
| 190 |
|
| 191 |
/* |
| 192 |
* This is split into two steps: the first step handles an overlapping |
| 193 |
* segment with address <= new address, and the second step handles |
| 194 |
* overlapping segments with address > new address. In some cases, we |
| 195 |
* can steal an existing segment instead of allocating a new one. |
| 196 |
*/ |
| 197 |
|
| 198 |
struct drgn_memory_segment *stolen = NULL, *segment; |
| 199 |
struct drgn_memory_segment *truncate_head = NULL, *truncate_tail = NULL; |
| 200 |
struct drgn_memory_segment_tree_iterator it = |
| 201 |
drgn_memory_segment_tree_search_le(tree, &min_address); |
| 202 |
if (it.entry) { |
| 203 |
if (max_address < it.entry->max_address) { |
| 204 |
/* |
| 205 |
* The new segment lies entirely within an existing |
| 206 |
* segment, and part of the existing segment extends |
| 207 |
* after the new segment (a "tail"). |
| 208 |
*/ |
| 209 |
struct drgn_memory_segment *tail = |
| 210 |
malloc(sizeof(*tail)); |
| 211 |
if (!tail) |
| 212 |
return &drgn_enomem; |
| 213 |
|
| 214 |
if (it.entry->min_address == min_address) { |
| 215 |
/* |
| 216 |
* The new segment starts at the same address as |
| 217 |
* the existing segment, so we can steal the |
| 218 |
* existing segment and just add the tail. |
| 219 |
*/ |
| 220 |
stolen = segment = it.entry; |
| 221 |
} else { |
| 222 |
/* |
| 223 |
* Part of the existing segment extends before |
| 224 |
* the new segment. We have to create the new |
| 225 |
* segment and truncate the existing segment. |
| 226 |
*/ |
| 227 |
segment = malloc(sizeof(*segment)); |
| 228 |
if (!segment) { |
| 229 |
free(tail); |
| 230 |
return &drgn_enomem; |
| 231 |
} |
| 232 |
truncate_tail = it.entry; |
| 233 |
} |
| 234 |
|
| 235 |
tail->min_address = max_address + 1; |
| 236 |
tail->max_address = it.entry->max_address; |
| 237 |
tail->orig_min_address = it.entry->orig_min_address; |
| 238 |
tail->read_fn = it.entry->read_fn; |
| 239 |
tail->arg = it.entry->arg; |
| 240 |
|
| 241 |
drgn_memory_segment_tree_insert(tree, tail, NULL); |
| 242 |
goto insert; |
| 243 |
} |
| 244 |
if (it.entry->min_address == min_address) { |
| 245 |
/* |
| 246 |
* The new segment subsumes an existing segment at the |
| 247 |
* same address. We can steal the existing segment. |
| 248 |
*/ |
| 249 |
stolen = it.entry; |
| 250 |
} else if (min_address <= it.entry->max_address) { |
| 251 |
/* |
| 252 |
* The new segment overlaps an existing segment before |
| 253 |
* it, and part of the existing segment extends before |
| 254 |
* the new segment. We need to truncate the existing |
| 255 |
* segment. |
| 256 |
*/ |
| 257 |
truncate_tail = it.entry; |
| 258 |
} else { |
| 259 |
/* |
| 260 |
* The new segment does not overlap any existing |
| 261 |
* segments before it. |
| 262 |
*/ |
| 263 |
} |
| 264 |
it = drgn_memory_segment_tree_next(it); |
| 265 |
} else { |
| 266 |
/* The new segment will be the new first segment. */ |
| 267 |
it = drgn_memory_segment_tree_first(tree); |
| 268 |
} |
| 269 |
|
| 270 |
while (it.entry) { |
| 271 |
if (max_address >= it.entry->max_address) { |
| 272 |
/* |
| 273 |
* The new segment subsumes an existing segment after |
| 274 |
* it. |
| 275 |
*/ |
| 276 |
if (stolen) { |
| 277 |
/* |
| 278 |
* We already stole a segment. We can delete the |
| 279 |
* existing segment. Since we won't try to |
| 280 |
* allocate a new segment later, it's safe to |
| 281 |
* modify the tree now. |
| 282 |
*/ |
| 283 |
struct drgn_memory_segment *existing_segment = it.entry; |
| 284 |
it = drgn_memory_segment_tree_delete_iterator(tree, it); |
| 285 |
free(existing_segment); |
| 286 |
} else { |
| 287 |
/* |
| 288 |
* We haven't stolen a segment yet, so steal |
| 289 |
* this one. |
| 290 |
* |
| 291 |
* This segment is the first existing segment |
| 292 |
* that starts after the new segment, and the |
| 293 |
* previous existing segment must start before |
| 294 |
* the new segment (otherwise we would've stolen |
| 295 |
* it). Therefore, this won't disturb the tree |
| 296 |
* order. |
| 297 |
*/ |
| 298 |
stolen = it.entry; |
| 299 |
it = drgn_memory_segment_tree_next(it); |
| 300 |
} |
| 301 |
continue; |
| 302 |
} |
| 303 |
if (max_address >= it.entry->min_address) { |
| 304 |
/* |
| 305 |
* The new segment overlaps an existing segment after |
| 306 |
* it, and part of the existing segment extends after |
| 307 |
* the new segment. We need to truncate the beginning of |
| 308 |
* the existing segment. |
| 309 |
*/ |
| 310 |
truncate_head = it.entry; |
| 311 |
} |
| 312 |
/* |
| 313 |
* The existing segment ends after the new segment ends. We're |
| 314 |
* done. |
| 315 |
*/ |
| 316 |
break; |
| 317 |
} |
| 318 |
|
| 319 |
if (stolen) { |
| 320 |
segment = stolen; |
| 321 |
} else { |
| 322 |
segment = malloc(sizeof(*segment)); |
| 323 |
if (!segment) |
| 324 |
return &drgn_enomem; |
| 325 |
} |
| 326 |
insert: |
| 327 |
/* |
| 328 |
* Now that we've allocated the new segment if necessary, we can safely |
| 329 |
* modify the tree. |
| 330 |
*/ |
| 331 |
if (truncate_head) |
| 332 |
truncate_head->min_address = max_address + 1; |
| 333 |
if (truncate_tail) |
| 334 |
truncate_tail->max_address = min_address - 1; |
| 335 |
segment->min_address = segment->orig_min_address = min_address; |
| 336 |
segment->max_address = max_address; |
| 337 |
segment->read_fn = read_fn; |
| 338 |
segment->arg = arg; |
| 339 |
/* If the segment is stolen, then it's already in the tree. */ |
| 340 |
if (!stolen) |
| 341 |
drgn_memory_segment_tree_insert(tree, segment, NULL); |
| 342 |
return NULL; |
| 343 |
} |
| 344 |
|
| 345 |
struct drgn_error *drgn_memory_reader_read(struct drgn_memory_reader *reader, |
| 346 |
void *buf, uint64_t address, |
| 347 |
size_t count, bool physical) |
| 348 |
{ |
| 349 |
assert(count == 0 || count - 1 <= UINT64_MAX - address); |
| 350 |
|
| 351 |
struct drgn_error *err; |
| 352 |
struct drgn_memory_segment_tree *tree = (physical ? |
| 353 |
&reader->physical_segments : |
| 354 |
&reader->virtual_segments); |
| 355 |
char *p = buf; |
| 356 |
while (count > 0) { |
| 357 |
struct drgn_memory_segment *segment = |
| 358 |
drgn_memory_segment_tree_search_le(tree, |
| 359 |
&address).entry; |
| 360 |
if (!segment || segment->max_address < address) { |
| 361 |
return drgn_error_format_fault(address, |
| 362 |
"could not find %smemory segment", |
| 363 |
physical ? "physical " : ""); |
| 364 |
} |
| 365 |
|
| 366 |
size_t n = min((uint64_t)(count - 1), |
| 367 |
segment->max_address - address) + 1; |
| 368 |
err = segment->read_fn(p, address, n, |
| 369 |
address - segment->orig_min_address, |
| 370 |
segment->arg, physical); |
| 371 |
if (err) |
| 372 |
return err; |
| 373 |
p += n; |
| 374 |
address += n; |
| 375 |
count -= n; |
| 376 |
} |
| 377 |
return NULL; |
| 378 |
} |
| 379 |
|
| 380 |
struct drgn_error *drgn_read_memory_file(void *buf, uint64_t address, |
| 381 |
size_t count, uint64_t offset, |
| 382 |
void *arg, bool physical) |
| 383 |
{ |
| 384 |
struct drgn_memory_file_segment *file_segment = arg; |
| 385 |
size_t file_count; |
| 386 |
if (offset < file_segment->file_size) { |
| 387 |
file_count = min((uint64_t)count, |
| 388 |
file_segment->file_size - offset); |
| 389 |
} else { |
| 390 |
file_count = 0; |
| 391 |
} |
| 392 |
size_t zero_count = count - file_count; |
| 393 |
if (!file_segment->zerofill && zero_count > 0) { |
| 394 |
return drgn_error_create_fault("memory not saved in core dump", |
| 395 |
address + file_count); |
| 396 |
} |
| 397 |
|
| 398 |
uint64_t file_offset = file_segment->file_offset + offset; |
| 399 |
char *p = buf; |
| 400 |
while (file_count) { |
| 401 |
ssize_t ret = pread(file_segment->fd, p, file_count, file_offset); |
| 402 |
if (ret == -1) { |
| 403 |
if (errno == EINTR) { |
| 404 |
continue; |
| 405 |
} else if (errno == EIO && file_segment->eio_is_fault) { |
| 406 |
return drgn_error_create_fault("could not read memory", |
| 407 |
address); |
| 408 |
} else { |
| 409 |
return drgn_error_create_os("pread", errno, NULL); |
| 410 |
} |
| 411 |
} else if (ret == 0) { |
| 412 |
return drgn_error_create_fault("short read from memory file", |
| 413 |
address); |
| 414 |
} |
| 415 |
p += ret; |
| 416 |
address += ret; |
| 417 |
file_count -= ret; |
| 418 |
file_offset += ret; |
| 419 |
} |
| 420 |
memset(p, '\0', zero_count); |
| 421 |
return NULL; |
| 422 |
} |
| 423 |
|
| 424 |
struct drgn_memory_search_iterator { |
| 425 |
struct drgn_program *prog; |
| 426 |
|
| 427 |
enum { |
| 428 |
DRGN_MEMORY_SEARCH_ITERATOR_MODE_MEMMEM, |
| 429 |
#define X(bits) DRGN_MEMORY_SEARCH_ITERATOR_MODE_U##bits, \ |
| 430 |
DRGN_MEMORY_SEARCH_ITERATOR_MODE_U##bits##_MULTI, |
| 431 |
SEARCH_MEMORY_UINT_SIZES |
| 432 |
#undef X |
| 433 |
#ifdef WITH_PCRE2 |
| 434 |
DRGN_MEMORY_SEARCH_ITERATOR_MODE_REGEX, |
| 435 |
#endif |
| 436 |
} mode; |
| 437 |
|
| 438 |
union { |
| 439 |
struct { |
| 440 |
void *needle; |
| 441 |
size_t size; |
| 442 |
uint64_t alignment_mask; |
| 443 |
} memmem; |
| 444 |
#define X(bits) \ |
| 445 |
uint##bits##_t u##bits; \ |
| 446 |
struct { \ |
| 447 |
uint##bits##_t *values; \ |
| 448 |
size_t num_values; \ |
| 449 |
uint##bits##_t mask; \ |
| 450 |
uint##bits##_t (*ranges)[2]; \ |
| 451 |
size_t num_ranges; \ |
| 452 |
bool bswap; \ |
| 453 |
} u##bits##_multi; |
| 454 |
SEARCH_MEMORY_UINT_SIZES |
| 455 |
#undef X |
| 456 |
#ifdef WITH_PCRE2 |
| 457 |
struct { |
| 458 |
pcre2_code *code; |
| 459 |
pcre2_match_data *match_data; |
| 460 |
uint32_t min_length; |
| 461 |
uint32_t partial_option; |
| 462 |
uint32_t next_match_options; |
| 463 |
bool need_refill; |
| 464 |
bool utf8; |
| 465 |
} regex; |
| 466 |
#endif |
| 467 |
}; |
| 468 |
|
| 469 |
unsigned char *buf; |
| 470 |
size_t buf_available; |
| 471 |
size_t pos; |
| 472 |
uint64_t buf_address; |
| 473 |
|
| 474 |
size_t buf_capacity; |
| 475 |
// Round the end address of reads up to this alignment. |
| 476 |
size_t read_alignment_mask; |
| 477 |
|
| 478 |
uint64_t min_address; |
| 479 |
uint64_t max_address; |
| 480 |
uint64_t address_offset; |
| 481 |
// -1 if address range is not set yet. |
| 482 |
int physical; |
| 483 |
}; |
| 484 |
|
| 485 |
static inline uint64_t align_down_mask(uint64_t value, uint64_t mask) |
| 486 |
{ |
| 487 |
return value & ~mask; |
| 488 |
} |
| 489 |
|
| 490 |
static inline uint64_t align_up_mask(uint64_t value, uint64_t mask) |
| 491 |
{ |
| 492 |
return (value + mask) & ~mask; |
| 493 |
} |
| 494 |
|
| 495 |
static struct drgn_memory_search_iterator * |
| 496 |
drgn_memory_search_iterator_create_common(struct drgn_program *prog, |
| 497 |
size_t refill_size, |
| 498 |
uint64_t alignment_mask) |
| 499 |
{ |
| 500 |
// Reading memory tends to be slow, so whenever we read from memory, we |
| 501 |
// buffer some extra. Instead of reading ahead a fixed amount, we read |
| 502 |
// to the next boundary of some power of two. |
| 503 |
// |
| 504 |
// We start with a generous alignment that was found to give good |
| 505 |
// throughput in most scenarios. If we're searching for a large string, |
| 506 |
// then we want at least double its size so that we can check a couple |
| 507 |
// of candidates per read. |
| 508 |
static const size_t default_read_alignment = 64 * 1024; |
| 509 |
size_t read_alignment; |
| 510 |
if (refill_size <= default_read_alignment / 2) |
| 511 |
read_alignment = default_read_alignment; |
| 512 |
else if (refill_size <= SIZE_MAX / 4 + 1) |
| 513 |
read_alignment = next_power_of_two(refill_size) * 2; |
| 514 |
else // Would overflow. |
| 515 |
return NULL; |
| 516 |
|
| 517 |
struct drgn_memory_search_iterator *it = malloc(sizeof(*it)); |
| 518 |
if (!it) |
| 519 |
return NULL; |
| 520 |
it->prog = prog; |
| 521 |
|
| 522 |
// The largest amount that we will buffer occurs when a read crosses a |
| 523 |
// read alignment boundary with as much as possible before the boundary. |
| 524 |
it->buf_capacity = align_down_mask(refill_size - 1, alignment_mask) |
| 525 |
+ read_alignment; |
| 526 |
it->buf = malloc(it->buf_capacity); |
| 527 |
if (!it->buf) { |
| 528 |
free(it); |
| 529 |
return NULL; |
| 530 |
} |
| 531 |
it->read_alignment_mask = read_alignment - 1; |
| 532 |
it->physical = -1; |
| 533 |
return it; |
| 534 |
} |
| 535 |
|
| 536 |
LIBDRGN_PUBLIC void |
| 537 |
drgn_memory_search_iterator_destroy(struct drgn_memory_search_iterator *it) |
| 538 |
{ |
| 539 |
if (!it) |
| 540 |
return; |
| 541 |
SWITCH_ENUM(it->mode) { |
| 542 |
case DRGN_MEMORY_SEARCH_ITERATOR_MODE_MEMMEM: |
| 543 |
free(it->memmem.needle); |
| 544 |
break; |
| 545 |
#define X(bits) \ |
| 546 |
case DRGN_MEMORY_SEARCH_ITERATOR_MODE_U##bits: \ |
| 547 |
break; \ |
| 548 |
case DRGN_MEMORY_SEARCH_ITERATOR_MODE_U##bits##_MULTI: \ |
| 549 |
free(it->u##bits##_multi.ranges); \ |
| 550 |
free(it->u##bits##_multi.values); \ |
| 551 |
break; |
| 552 |
SEARCH_MEMORY_UINT_SIZES |
| 553 |
#undef X |
| 554 |
#ifdef WITH_PCRE2 |
| 555 |
case DRGN_MEMORY_SEARCH_ITERATOR_MODE_REGEX: |
| 556 |
pcre2_match_data_free(it->regex.match_data); |
| 557 |
pcre2_code_free(it->regex.code); |
| 558 |
break; |
| 559 |
#endif |
| 560 |
default: |
| 561 |
UNREACHABLE(); |
| 562 |
} |
| 563 |
free(it->buf); |
| 564 |
free(it); |
| 565 |
} |
| 566 |
|
| 567 |
LIBDRGN_PUBLIC struct drgn_program * |
| 568 |
drgn_memory_search_iterator_program(const struct drgn_memory_search_iterator *it) |
| 569 |
{ |
| 570 |
return it->prog; |
| 571 |
} |
| 572 |
|
| 573 |
static inline size_t |
| 574 |
drgn_memory_search_iterator_remaining_bytes(struct drgn_memory_search_iterator *it) |
| 575 |
{ |
| 576 |
return it->buf_available - it->pos; |
| 577 |
} |
| 578 |
|
| 579 |
static inline bool |
| 580 |
drgn_memory_search_iterator_calc_buf_target(struct drgn_memory_search_iterator *it, |
| 581 |
size_t needed, size_t *ret) |
| 582 |
{ |
| 583 |
if (needed - 1 > it->max_address - it->buf_address) |
| 584 |
return false; |
| 585 |
|
| 586 |
// This calculation still works if it->buf_address + needed wraps to 0. |
| 587 |
uint64_t max_address = align_up_mask(it->buf_address + needed, |
| 588 |
it->read_alignment_mask) - 1; |
| 589 |
if (max_address > it->max_address) |
| 590 |
max_address = it->max_address; |
| 591 |
|
| 592 |
assert(max_address - it->buf_address < SIZE_MAX); |
| 593 |
*ret = max_address - it->buf_address + 1; |
| 594 |
return true; |
| 595 |
} |
| 596 |
|
| 597 |
static struct drgn_error * |
| 598 |
drgn_memory_search_iterator_refill(struct drgn_memory_search_iterator *it, |
| 599 |
drgn_blocking_state *blocking_state, |
| 600 |
size_t needed, uint64_t alignment_mask, |
| 601 |
bool *gap_ret) |
| 602 |
{ |
| 603 |
struct drgn_error *err; |
| 604 |
struct drgn_memory_segment_tree *tree = |
| 605 |
it->physical ? &it->prog->reader.physical_segments |
| 606 |
: &it->prog->reader.virtual_segments; |
| 607 |
|
| 608 |
if (drgn_memory_search_iterator_remaining_bytes(it) >= needed) |
| 609 |
return NULL; |
| 610 |
|
| 611 |
err = drgn_blocking_check_signals(blocking_state); |
| 612 |
if (err) |
| 613 |
return err; |
| 614 |
|
| 615 |
// Stop if we've reached the maximum addresses, being very careful about |
| 616 |
// overflow: if max_address == UINT64_MAX, then buf_address + pos can |
| 617 |
// overflow. Additionally, if buf_address + pos is close to UINT64_MAX, |
| 618 |
// then aligning that up could overflow. Instead, note that anything |
| 619 |
// above max_address, aligned down, would get aligned up to beyond |
| 620 |
// max_address (or overflow). |
| 621 |
uint64_t new_buf_address; |
| 622 |
if (__builtin_add_overflow(it->buf_address, it->pos, &new_buf_address) |
| 623 |
|| new_buf_address > align_down_mask(it->max_address, alignment_mask)) |
| 624 |
return &drgn_stop; |
| 625 |
new_buf_address = align_up_mask(new_buf_address, alignment_mask); |
| 626 |
|
| 627 |
// If there's anything left at the end of the buffer, move it to the |
| 628 |
// beginning. |
| 629 |
if (new_buf_address - it->buf_address < it->buf_available) { |
| 630 |
size_t remaining = |
| 631 |
it->buf_available - (new_buf_address - it->buf_address); |
| 632 |
memmove(it->buf, it->buf + (new_buf_address - it->buf_address), |
| 633 |
remaining); |
| 634 |
it->buf_available = remaining; |
| 635 |
} else { |
| 636 |
it->buf_available = 0; |
| 637 |
} |
| 638 |
it->buf_address = new_buf_address; |
| 639 |
it->pos = 0; |
| 640 |
|
| 641 |
for (;;) { |
| 642 |
size_t target; |
| 643 |
if (!drgn_memory_search_iterator_calc_buf_target(it, needed, |
| 644 |
&target)) |
| 645 |
return &drgn_stop; |
| 646 |
assert(target <= it->buf_capacity); |
| 647 |
|
| 648 |
for (;;) { |
| 649 |
uint64_t address = it->buf_address + it->buf_available; |
| 650 |
|
| 651 |
auto tree_it = |
| 652 |
drgn_memory_segment_tree_search_le(tree, &address); |
| 653 |
if (!tree_it.entry || tree_it.entry->max_address < address) { |
| 654 |
// We encountered a gap in the address space. |
| 655 |
if (it->buf_available >= needed) { |
| 656 |
// We read enough data before the gap. |
| 657 |
// Return it now. |
| 658 |
*gap_ret = true; |
| 659 |
return NULL; |
| 660 |
} |
| 661 |
|
| 662 |
// Skip to the next memory segment and start over. |
| 663 |
if (tree_it.entry) |
| 664 |
tree_it = drgn_memory_segment_tree_next(tree_it); |
| 665 |
else |
| 666 |
tree_it = drgn_memory_segment_tree_first(tree); |
| 667 |
// This mirrors the new_buf_address checks |
| 668 |
// above. |
| 669 |
if (!tree_it.entry |
| 670 |
|| tree_it.entry->min_address |
| 671 |
> align_down_mask(it->max_address, |
| 672 |
alignment_mask)) |
| 673 |
return &drgn_stop; |
| 674 |
it->buf_address = |
| 675 |
align_up_mask(tree_it.entry->min_address, |
| 676 |
alignment_mask); |
| 677 |
it->buf_available = 0; |
| 678 |
break; |
| 679 |
} |
| 680 |
|
| 681 |
struct drgn_memory_segment *segment = tree_it.entry; |
| 682 |
size_t n = target - it->buf_available; |
| 683 |
if (n - 1 > segment->max_address - address) |
| 684 |
n = segment->max_address - address + 1; |
| 685 |
err = segment->read_fn(it->buf + it->buf_available, |
| 686 |
address, n, |
| 687 |
address - segment->orig_min_address, |
| 688 |
segment->arg, it->physical); |
| 689 |
if (err) |
| 690 |
return err; |
| 691 |
it->buf_available += n; |
| 692 |
if (it->buf_available == target) { |
| 693 |
*gap_ret = false; |
| 694 |
return NULL; |
| 695 |
} |
| 696 |
} |
| 697 |
} |
| 698 |
} |
| 699 |
|
| 700 |
#define X(bits) \ |
| 701 |
static struct drgn_memory_search_iterator * \ |
| 702 |
drgn_program_search_memory_u##bits##_no_bswap(struct drgn_program *prog, \ |
| 703 |
uint##bits##_t value) \ |
| 704 |
{ \ |
| 705 |
struct drgn_memory_search_iterator *it = \ |
| 706 |
drgn_memory_search_iterator_create_common(prog, sizeof(value), \ |
| 707 |
sizeof(value) - 1); \ |
| 708 |
if (!it) \ |
| 709 |
return NULL; \ |
| 710 |
it->mode = DRGN_MEMORY_SEARCH_ITERATOR_MODE_U##bits; \ |
| 711 |
it->u##bits = value; \ |
| 712 |
return it; \ |
| 713 |
} \ |
| 714 |
\ |
| 715 |
LIBDRGN_PUBLIC struct drgn_error * \ |
| 716 |
drgn_program_search_memory_u##bits(struct drgn_program *prog, \ |
| 717 |
uint##bits##_t value, \ |
| 718 |
struct drgn_memory_search_iterator **ret) \ |
| 719 |
{ \ |
| 720 |
struct drgn_error *err; \ |
| 721 |
bool bswap; \ |
| 722 |
err = drgn_program_bswap(prog, &bswap); \ |
| 723 |
if (err) \ |
| 724 |
return err; \ |
| 725 |
/* \ |
| 726 |
* Save the value in host byte order so that we don't need to byte swap \ |
| 727 |
* every read value. \ |
| 728 |
*/ \ |
| 729 |
if (bswap) \ |
| 730 |
value = bswap_##bits(value); \ |
| 731 |
struct drgn_memory_search_iterator *it = \ |
| 732 |
drgn_program_search_memory_u##bits##_no_bswap(prog, value); \ |
| 733 |
if (!it) \ |
| 734 |
return &drgn_enomem; \ |
| 735 |
*ret = it; \ |
| 736 |
return NULL; \ |
| 737 |
} \ |
| 738 |
\ |
| 739 |
static struct drgn_error * \ |
| 740 |
drgn_memory_search_iterator_next_u##bits(struct drgn_memory_search_iterator *it,\ |
| 741 |
drgn_blocking_state *blocking_state, \ |
| 742 |
uint64_t *addr_ret, \ |
| 743 |
const void **match_ret, \ |
| 744 |
size_t *match_len_ret) \ |
| 745 |
{ \ |
| 746 |
struct drgn_error *err; \ |
| 747 |
for (;;) { \ |
| 748 |
bool unused; \ |
| 749 |
err = drgn_memory_search_iterator_refill(it, blocking_state, \ |
| 750 |
sizeof(uint##bits##_t),\ |
| 751 |
sizeof(uint##bits##_t) - 1,\ |
| 752 |
&unused); \ |
| 753 |
if (err) \ |
| 754 |
return err; \ |
| 755 |
\ |
| 756 |
size_t n = it->buf_available / sizeof(uint##bits##_t); \ |
| 757 |
for (size_t i = it->pos / sizeof(uint##bits##_t); i < n; i++) { \ |
| 758 |
if (((uint##bits##_t *)it->buf)[i] == it->u##bits) { \ |
| 759 |
if (addr_ret) { \ |
| 760 |
*addr_ret = it->buf_address \ |
| 761 |
+ i * sizeof(uint##bits##_t)\ |
| 762 |
+ it->address_offset; \ |
| 763 |
} \ |
| 764 |
if (match_ret) \ |
| 765 |
*match_ret = &((uint##bits##_t *)it->buf)[i];\ |
| 766 |
if (match_len_ret) \ |
| 767 |
*match_len_ret = sizeof(uint##bits##_t);\ |
| 768 |
it->pos = (i + 1) * sizeof(uint##bits##_t); \ |
| 769 |
return NULL; \ |
| 770 |
} \ |
| 771 |
} \ |
| 772 |
it->pos = it->buf_available; \ |
| 773 |
} \ |
| 774 |
} \ |
| 775 |
\ |
| 776 |
LIBDRGN_PUBLIC struct drgn_error * \ |
| 777 |
drgn_program_search_memory_u##bits##_multi(struct drgn_program *prog, \ |
| 778 |
const uint##bits##_t *values, \ |
| 779 |
size_t num_values, \ |
| 780 |
uint##bits##_t ignore_mask, \ |
| 781 |
const uint##bits##_t (*ranges)[2], \ |
| 782 |
size_t num_ranges, \ |
| 783 |
struct drgn_memory_search_iterator **ret)\ |
| 784 |
{ \ |
| 785 |
struct drgn_error *err; \ |
| 786 |
/* Trivial cases that we can optimize as single-value searches. */ \ |
| 787 |
if (num_values == 1 && num_ranges == 0 && ignore_mask == 0) { \ |
| 788 |
return drgn_program_search_memory_u##bits(prog, values[0], ret);\ |
| 789 |
} \ |
| 790 |
if (num_values == 0 && num_ranges == 1 \ |
| 791 |
&& ranges[0][0] == ranges[0][1]) { \ |
| 792 |
return drgn_program_search_memory_u##bits(prog, ranges[0][0], \ |
| 793 |
ret); \ |
| 794 |
} \ |
| 795 |
if (num_values == 0 && num_ranges == 0) { \ |
| 796 |
return drgn_error_create(DRGN_ERROR_INVALID_ARGUMENT, \ |
| 797 |
"at least one value or range is required");\ |
| 798 |
} \ |
| 799 |
\ |
| 800 |
/* \ |
| 801 |
* For values, we save everything in host byte order so that we don't \ |
| 802 |
* need to byte swap read values. For ranges, we have to save the \ |
| 803 |
* original range values and byte swap every read value. \ |
| 804 |
*/ \ |
| 805 |
bool bswap; \ |
| 806 |
err = drgn_program_bswap(prog, &bswap); \ |
| 807 |
if (err) \ |
| 808 |
return err; \ |
| 809 |
\ |
| 810 |
_cleanup_free_ uint##bits##_t *values_copy = NULL; \ |
| 811 |
if (num_values > 0) { \ |
| 812 |
values_copy = memdup(values, num_values * sizeof(values[0])); \ |
| 813 |
if (!values_copy) \ |
| 814 |
return &drgn_enomem; \ |
| 815 |
\ |
| 816 |
if (ignore_mask) { \ |
| 817 |
for (size_t i = 0; i < num_values; i++) \ |
| 818 |
values_copy[i] &= ~ignore_mask; \ |
| 819 |
} \ |
| 820 |
if (bswap) { \ |
| 821 |
for (size_t i = 0; i < num_values; i++) \ |
| 822 |
values_copy[i] = bswap_##bits(values_copy[i]); \ |
| 823 |
ignore_mask = bswap_##bits(ignore_mask); \ |
| 824 |
} \ |
| 825 |
} \ |
| 826 |
\ |
| 827 |
_cleanup_free_ uint##bits##_t (*ranges_copy)[2] = NULL; \ |
| 828 |
if (num_ranges > 0) { \ |
| 829 |
ranges_copy = memdup(ranges, num_ranges * sizeof(ranges[0])); \ |
| 830 |
if (!ranges_copy) \ |
| 831 |
return &drgn_enomem; \ |
| 832 |
} \ |
| 833 |
\ |
| 834 |
struct drgn_memory_search_iterator *it = \ |
| 835 |
drgn_memory_search_iterator_create_common( \ |
| 836 |
prog, sizeof(uint##bits##_t), sizeof(uint##bits##_t) - 1);\ |
| 837 |
if (!it) \ |
| 838 |
return &drgn_enomem; \ |
| 839 |
\ |
| 840 |
it->mode = DRGN_MEMORY_SEARCH_ITERATOR_MODE_U##bits##_MULTI; \ |
| 841 |
it->u##bits##_multi.values = no_cleanup_ptr(values_copy); \ |
| 842 |
it->u##bits##_multi.num_values = num_values; \ |
| 843 |
it->u##bits##_multi.mask = ~ignore_mask; \ |
| 844 |
it->u##bits##_multi.ranges = no_cleanup_ptr(ranges_copy); \ |
| 845 |
it->u##bits##_multi.num_ranges = num_ranges; \ |
| 846 |
it->u##bits##_multi.bswap = bswap; \ |
| 847 |
*ret = it; \ |
| 848 |
return NULL; \ |
| 849 |
} \ |
| 850 |
\ |
| 851 |
static inline bool \ |
| 852 |
drgn_memory_search_iterator_u##bits##_multi_match(struct drgn_memory_search_iterator *it,\ |
| 853 |
uint##bits##_t raw_value) \ |
| 854 |
{ \ |
| 855 |
uint##bits##_t masked_value = raw_value & it->u##bits##_multi.mask; \ |
| 856 |
for (size_t i = 0; i < it->u##bits##_multi.num_values; i++) { \ |
| 857 |
if (masked_value == it->u##bits##_multi.values[i]) \ |
| 858 |
return true; \ |
| 859 |
} \ |
| 860 |
\ |
| 861 |
if (it->u##bits##_multi.num_ranges > 0) { \ |
| 862 |
uint##bits##_t value = raw_value; \ |
| 863 |
if (it->u##bits##_multi.bswap) \ |
| 864 |
value = bswap_##bits(value); \ |
| 865 |
for (size_t i = 0; i < it->u##bits##_multi.num_ranges; i++) { \ |
| 866 |
uint##bits##_t *range = it->u##bits##_multi.ranges[i]; \ |
| 867 |
if (range[0] <= value && value <= range[1]) \ |
| 868 |
return true; \ |
| 869 |
} \ |
| 870 |
} \ |
| 871 |
return false; \ |
| 872 |
} \ |
| 873 |
\ |
| 874 |
static struct drgn_error * \ |
| 875 |
drgn_memory_search_iterator_next_u##bits##_multi(struct drgn_memory_search_iterator *it,\ |
| 876 |
drgn_blocking_state *blocking_state,\ |
| 877 |
uint64_t *addr_ret, \ |
| 878 |
const void **match_ret, \ |
| 879 |
size_t *match_len_ret) \ |
| 880 |
{ \ |
| 881 |
struct drgn_error *err; \ |
| 882 |
for (;;) { \ |
| 883 |
bool gap; \ |
| 884 |
err = drgn_memory_search_iterator_refill(it, \ |
| 885 |
blocking_state, \ |
| 886 |
sizeof(uint##bits##_t),\ |
| 887 |
sizeof(uint##bits##_t) - 1,\ |
| 888 |
&gap); \ |
| 889 |
if (err) \ |
| 890 |
return err; \ |
| 891 |
\ |
| 892 |
size_t n = it->buf_available / sizeof(uint##bits##_t); \ |
| 893 |
for (size_t i = it->pos / sizeof(uint##bits##_t); i < n; i++) { \ |
| 894 |
if (drgn_memory_search_iterator_u##bits##_multi_match( \ |
| 895 |
it, ((uint##bits##_t *)it->buf)[i])) { \ |
| 896 |
if (addr_ret) { \ |
| 897 |
*addr_ret = it->buf_address \ |
| 898 |
+ i * sizeof(uint##bits##_t)\ |
| 899 |
+ it->address_offset; \ |
| 900 |
} \ |
| 901 |
if (match_ret) \ |
| 902 |
*match_ret = &((uint##bits##_t *)it->buf)[i];\ |
| 903 |
if (match_len_ret) \ |
| 904 |
*match_len_ret = sizeof(uint##bits##_t);\ |
| 905 |
it->pos = (i + 1) * sizeof(uint##bits##_t); \ |
| 906 |
return NULL; \ |
| 907 |
} \ |
| 908 |
} \ |
| 909 |
it->pos = it->buf_available; \ |
| 910 |
} \ |
| 911 |
} |
| 912 |
SEARCH_MEMORY_UINT_SIZES |
| 913 |
#undef X |
| 914 |
|
| 915 |
LIBDRGN_PUBLIC struct drgn_error * |
| 916 |
drgn_program_search_memory_word(struct drgn_program *prog, uint64_t value, |
| 917 |
struct drgn_memory_search_iterator **ret) |
| 918 |
{ |
| 919 |
struct drgn_error *err; |
| 920 |
bool is_64_bit; |
| 921 |
err = drgn_program_is_64_bit(prog, &is_64_bit); |
| 922 |
if (err) |
| 923 |
return err; |
| 924 |
if (is_64_bit) { |
| 925 |
return drgn_program_search_memory_u64(prog, value, ret); |
| 926 |
} else { |
| 927 |
if (value > UINT32_MAX) { |
| 928 |
return drgn_error_create(DRGN_ERROR_OVERFLOW, |
| 929 |
"value is too large"); |
| 930 |
} |
| 931 |
return drgn_program_search_memory_u32(prog, value, ret); |
| 932 |
} |
| 933 |
} |
| 934 |
|
| 935 |
LIBDRGN_PUBLIC struct drgn_error * |
| 936 |
drgn_program_search_memory_word_multi(struct drgn_program *prog, |
| 937 |
const uint64_t *values, size_t num_values, |
| 938 |
uint64_t ignore_mask, |
| 939 |
const uint64_t (*ranges)[2], |
| 940 |
size_t num_ranges, |
| 941 |
struct drgn_memory_search_iterator **ret) |
| 942 |
{ |
| 943 |
struct drgn_error *err; |
| 944 |
bool is_64_bit; |
| 945 |
err = drgn_program_is_64_bit(prog, &is_64_bit); |
| 946 |
if (err) |
| 947 |
return err; |
| 948 |
if (is_64_bit) { |
| 949 |
return drgn_program_search_memory_u64_multi(prog, values, |
| 950 |
num_values, |
| 951 |
ignore_mask, ranges, |
| 952 |
num_ranges, ret); |
| 953 |
} |
| 954 |
|
| 955 |
_cleanup_free_ uint32_t *values32 = NULL; |
| 956 |
if (num_values > 0) { |
| 957 |
values32 = malloc_array(num_values, sizeof(values32[0])); |
| 958 |
if (!values32) |
| 959 |
return &drgn_enomem; |
| 960 |
for (size_t i = 0; i < num_values; i++) { |
| 961 |
if (values[i] > UINT32_MAX) { |
| 962 |
return drgn_error_create(DRGN_ERROR_OVERFLOW, |
| 963 |
"value is too large"); |
| 964 |
} |
| 965 |
values32[i] = values[i]; |
| 966 |
} |
| 967 |
} |
| 968 |
|
| 969 |
if (ignore_mask > UINT32_MAX) { |
| 970 |
return drgn_error_create(DRGN_ERROR_OVERFLOW, |
| 971 |
"ignore_mask is too large"); |
| 972 |
} |
| 973 |
|
| 974 |
_cleanup_free_ uint32_t (*ranges32)[2] = NULL; |
| 975 |
if (num_ranges > 0) { |
| 976 |
ranges32 = malloc_array(num_ranges, sizeof(ranges32[0])); |
| 977 |
if (!ranges32) |
| 978 |
return &drgn_enomem; |
| 979 |
for (size_t i = 0; i < num_ranges; i++) { |
| 980 |
if (ranges[i][0] > UINT32_MAX |
| 981 |
|| ranges[i][1] > UINT32_MAX) { |
| 982 |
return drgn_error_create(DRGN_ERROR_OVERFLOW, |
| 983 |
"range values are too large"); |
| 984 |
} |
| 985 |
ranges32[i][0] = ranges[i][0]; |
| 986 |
ranges32[i][1] = ranges[i][1]; |
| 987 |
} |
| 988 |
} |
| 989 |
|
| 990 |
return drgn_program_search_memory_u32_multi(prog, values32, num_values, |
| 991 |
ignore_mask, ranges32, |
| 992 |
num_ranges, ret); |
| 993 |
} |
| 994 |
|
| 995 |
LIBDRGN_PUBLIC struct drgn_error * |
| 996 |
drgn_program_search_memory(struct drgn_program *prog, const void *needle, |
| 997 |
size_t size, uint64_t alignment, |
| 998 |
struct drgn_memory_search_iterator **ret) |
| 999 |
{ |
| 1000 |
struct drgn_memory_search_iterator *it; |
| 1001 |
|
| 1002 |
// Cases that we can optimize as aligned integer searches. |
| 1003 |
if (size == sizeof(uint32_t) && alignment == sizeof(uint32_t)) { |
| 1004 |
uint32_t value; |
| 1005 |
memcpy(&value, needle, sizeof(value)); |
| 1006 |
it = drgn_program_search_memory_u32_no_bswap(prog, value); |
| 1007 |
if (!it) |
| 1008 |
return &drgn_enomem; |
| 1009 |
*ret = it; |
| 1010 |
return NULL; |
| 1011 |
} |
| 1012 |
if (size == sizeof(uint64_t) && alignment == sizeof(uint64_t)) { |
| 1013 |
uint64_t value; |
| 1014 |
memcpy(&value, needle, sizeof(value)); |
| 1015 |
it = drgn_program_search_memory_u64_no_bswap(prog, value); |
| 1016 |
if (!it) |
| 1017 |
return &drgn_enomem; |
| 1018 |
*ret = it; |
| 1019 |
return NULL; |
| 1020 |
} |
| 1021 |
|
| 1022 |
if (size == 0) { |
| 1023 |
return drgn_error_create(DRGN_ERROR_INVALID_ARGUMENT, |
| 1024 |
"needle cannot be empty"); |
| 1025 |
} |
| 1026 |
if (!is_power_of_two(alignment)) { |
| 1027 |
return drgn_error_create(DRGN_ERROR_INVALID_ARGUMENT, |
| 1028 |
"alignment must be power of 2"); |
| 1029 |
} |
| 1030 |
|
| 1031 |
_cleanup_free_ void *needle_copy = memdup(needle, size); |
| 1032 |
if (!needle_copy) |
| 1033 |
return &drgn_enomem; |
| 1034 |
|
| 1035 |
it = drgn_memory_search_iterator_create_common(prog, size, |
| 1036 |
alignment - 1); |
| 1037 |
if (!it) |
| 1038 |
return &drgn_enomem; |
| 1039 |
|
| 1040 |
it->mode = DRGN_MEMORY_SEARCH_ITERATOR_MODE_MEMMEM; |
| 1041 |
it->memmem.needle = no_cleanup_ptr(needle_copy); |
| 1042 |
it->memmem.size = size; |
| 1043 |
it->memmem.alignment_mask = alignment - 1; |
| 1044 |
*ret = it; |
| 1045 |
return NULL; |
| 1046 |
} |
| 1047 |
|
| 1048 |
static struct drgn_error * |
| 1049 |
drgn_memory_search_iterator_next_memmem(struct drgn_memory_search_iterator *it, |
| 1050 |
drgn_blocking_state *blocking_state, |
| 1051 |
uint64_t *addr_ret, |
| 1052 |
const void **match_ret, |
| 1053 |
size_t *match_len_ret) |
| 1054 |
{ |
| 1055 |
struct drgn_error *err; |
| 1056 |
for (;;) { |
| 1057 |
bool gap; |
| 1058 |
err = drgn_memory_search_iterator_refill(it, blocking_state, |
| 1059 |
it->memmem.size, |
| 1060 |
it->memmem.alignment_mask, |
| 1061 |
&gap); |
| 1062 |
if (err) |
| 1063 |
return err; |
| 1064 |
|
| 1065 |
const unsigned char *match = |
| 1066 |
memmem(it->buf + it->pos, |
| 1067 |
drgn_memory_search_iterator_remaining_bytes(it), |
| 1068 |
it->memmem.needle, it->memmem.size); |
| 1069 |
if (match) { |
| 1070 |
uint64_t address = it->buf_address + (match - it->buf) |
| 1071 |
+ it->address_offset; |
| 1072 |
if ((address & it->memmem.alignment_mask) == 0) { |
| 1073 |
it->pos = match - it->buf + it->memmem.size; |
| 1074 |
if (addr_ret) |
| 1075 |
*addr_ret = address; |
| 1076 |
if (match_ret) |
| 1077 |
*match_ret = match; |
| 1078 |
if (match_len_ret) |
| 1079 |
*match_len_ret = it->memmem.size; |
| 1080 |
return NULL; |
| 1081 |
} |
| 1082 |
// Match wasn't aligned. Keep looking. |
| 1083 |
it->pos = (match - it->buf) + 1; |
| 1084 |
} else { |
| 1085 |
// No match found. We have to keep the last (size - 1) |
| 1086 |
// bytes in case a match starts in those bytes. |
| 1087 |
it->pos = it->buf_available - it->memmem.size + 1; |
| 1088 |
} |
| 1089 |
} |
| 1090 |
} |
| 1091 |
|
| 1092 |
LIBDRGN_PUBLIC struct drgn_error * |
| 1093 |
drgn_search_memory_for_object(const struct drgn_object *obj, |
| 1094 |
struct drgn_memory_search_iterator **ret) |
| 1095 |
{ |
| 1096 |
struct drgn_error *err; |
| 1097 |
struct drgn_memory_search_iterator *it; |
| 1098 |
|
| 1099 |
uint64_t size = drgn_object_size(obj); |
| 1100 |
uint64_t alignment; |
| 1101 |
err = drgn_type_alignof(drgn_object_qualified_type(obj), &alignment); |
| 1102 |
if (err) |
| 1103 |
return err; |
| 1104 |
|
| 1105 |
// Cases that we can optimize as aligned integer searches. |
| 1106 |
if (size == sizeof(uint32_t) && alignment == sizeof(uint32_t)) { |
| 1107 |
uint32_t value; |
| 1108 |
err = drgn_object_read_bytes(obj, &value); |
| 1109 |
if (err) |
| 1110 |
return err; |
| 1111 |
it = drgn_program_search_memory_u32_no_bswap(drgn_object_program(obj), |
| 1112 |
value); |
| 1113 |
if (!it) |
| 1114 |
return &drgn_enomem; |
| 1115 |
*ret = it; |
| 1116 |
return NULL; |
| 1117 |
} |
| 1118 |
if (size == sizeof(uint64_t) && alignment == sizeof(uint64_t)) { |
| 1119 |
uint64_t value; |
| 1120 |
err = drgn_object_read_bytes(obj, &value); |
| 1121 |
if (err) |
| 1122 |
return err; |
| 1123 |
it = drgn_program_search_memory_u64_no_bswap(drgn_object_program(obj), |
| 1124 |
value); |
| 1125 |
if (!it) |
| 1126 |
return &drgn_enomem; |
| 1127 |
*ret = it; |
| 1128 |
return NULL; |
| 1129 |
} |
| 1130 |
|
| 1131 |
if (size == 0) { |
| 1132 |
return drgn_error_create(DRGN_ERROR_INVALID_ARGUMENT, |
| 1133 |
"can't search for object with size 0"); |
| 1134 |
} |
| 1135 |
// Ignore the alignment if it's bogus. |
| 1136 |
if (!is_power_of_two(alignment)) |
| 1137 |
alignment = 1; |
| 1138 |
|
| 1139 |
_cleanup_free_ void *needle = malloc64(size); |
| 1140 |
if (!needle) |
| 1141 |
return &drgn_enomem; |
| 1142 |
err = drgn_object_read_bytes(obj, needle); |
| 1143 |
if (err) |
| 1144 |
return err; |
| 1145 |
|
| 1146 |
it = drgn_memory_search_iterator_create_common(drgn_object_program(obj), |
| 1147 |
size, alignment - 1); |
| 1148 |
if (!it) |
| 1149 |
return &drgn_enomem; |
| 1150 |
|
| 1151 |
it->mode = DRGN_MEMORY_SEARCH_ITERATOR_MODE_MEMMEM; |
| 1152 |
it->memmem.needle = no_cleanup_ptr(needle); |
| 1153 |
it->memmem.size = size; |
| 1154 |
it->memmem.alignment_mask = alignment - 1; |
| 1155 |
*ret = it; |
| 1156 |
return NULL; |
| 1157 |
} |
| 1158 |
|
| 1159 |
LIBDRGN_PUBLIC struct drgn_error * |
| 1160 |
drgn_program_search_memory_regex(struct drgn_program *prog, const void *pattern, |
| 1161 |
size_t pattern_len, bool utf8, |
| 1162 |
struct drgn_memory_search_iterator **ret) |
| 1163 |
{ |
| 1164 |
#ifdef WITH_PCRE2 |
| 1165 |
int errorcode; |
| 1166 |
PCRE2_SIZE erroroffset; |
| 1167 |
uint32_t options; |
| 1168 |
|
| 1169 |
#if PCRE2_MAJOR > 10 || (PCRE2_MAJOR == 10 && PCRE2_MINOR >= 34) |
| 1170 |
options = utf8 ? PCRE2_MATCH_INVALID_UTF : PCRE2_NEVER_UTF; |
| 1171 |
#else |
| 1172 |
if (utf8) |
| 1173 |
return drgn_error_format( |
| 1174 |
DRGN_ERROR_NOT_IMPLEMENTED, |
| 1175 |
"The PCRE2 version (%d.%d) is too old to support matching UTF-8 " |
| 1176 |
"patterns within invalid UTF-8 data. Use a bytes pattern, or " |
| 1177 |
"build against a newer PCRE2 version (10.34 or later).", |
| 1178 |
PCRE2_MAJOR, PCRE2_MINOR |
| 1179 |
); |
| 1180 |
options = PCRE2_NEVER_UTF; |
| 1181 |
#endif |
| 1182 |
_cleanup_pcre2_code_ pcre2_code *code = |
| 1183 |
pcre2_compile(pattern, pattern_len, options, |
| 1184 |
&errorcode, &erroroffset, NULL); |
| 1185 |
if (!code) |
| 1186 |
return drgn_error_pcre2(errorcode, &erroroffset); |
| 1187 |
errorcode = pcre2_jit_compile(code, |
| 1188 |
PCRE2_JIT_COMPLETE |
| 1189 |
| PCRE2_JIT_PARTIAL_HARD); |
| 1190 |
// PCRE2_ERROR_JIT_BADOPTION is returned if JIT is not supported. |
| 1191 |
if (errorcode && errorcode != PCRE2_ERROR_JIT_BADOPTION) |
| 1192 |
return drgn_error_pcre2(errorcode, NULL); |
| 1193 |
|
| 1194 |
uint32_t max_lookbehind; |
| 1195 |
errorcode = pcre2_pattern_info(code, PCRE2_INFO_MAXLOOKBEHIND, |
| 1196 |
&max_lookbehind); |
| 1197 |
if (errorcode) |
| 1198 |
return drgn_error_pcre2(errorcode, NULL); |
| 1199 |
if (max_lookbehind != 0) { |
| 1200 |
return drgn_error_create(DRGN_ERROR_INVALID_ARGUMENT, |
| 1201 |
"lookbehind is not allowed"); |
| 1202 |
} |
| 1203 |
|
| 1204 |
uint32_t min_length; |
| 1205 |
errorcode = pcre2_pattern_info(code, PCRE2_INFO_MINLENGTH, &min_length); |
| 1206 |
if (errorcode) |
| 1207 |
return drgn_error_pcre2(errorcode, NULL); |
| 1208 |
if (min_length == 0) |
| 1209 |
min_length = 1; |
| 1210 |
|
| 1211 |
_cleanup_pcre2_match_data_ pcre2_match_data *match_data = |
| 1212 |
pcre2_match_data_create(1, NULL); |
| 1213 |
if (!match_data) |
| 1214 |
return &drgn_enomem; |
| 1215 |
|
| 1216 |
struct drgn_memory_search_iterator *it = |
| 1217 |
drgn_memory_search_iterator_create_common(prog, min_length, 1); |
| 1218 |
if (!it) |
| 1219 |
return &drgn_enomem; |
| 1220 |
|
| 1221 |
it->mode = DRGN_MEMORY_SEARCH_ITERATOR_MODE_REGEX; |
| 1222 |
it->regex.code = no_cleanup_ptr(code); |
| 1223 |
it->regex.match_data = no_cleanup_ptr(match_data); |
| 1224 |
it->regex.min_length = min_length; |
| 1225 |
it->regex.utf8 = utf8; |
| 1226 |
*ret = it; |
| 1227 |
return NULL; |
| 1228 |
#else |
| 1229 |
return drgn_error_create(DRGN_ERROR_NOT_IMPLEMENTED, |
| 1230 |
"drgn was built without regular expression support"); |
| 1231 |
#endif |
| 1232 |
} |
| 1233 |
|
| 1234 |
#ifdef WITH_PCRE2 |
| 1235 |
static struct drgn_error * |
| 1236 |
drgn_memory_search_iterator_try_extend(struct drgn_memory_search_iterator *it, |
| 1237 |
bool *gap_ret) |
| 1238 |
{ |
| 1239 |
struct drgn_error *err; |
| 1240 |
struct drgn_memory_segment_tree *tree = |
| 1241 |
it->physical ? &it->prog->reader.physical_segments |
| 1242 |
: &it->prog->reader.virtual_segments; |
| 1243 |
|
| 1244 |
size_t target; |
| 1245 |
if (!drgn_memory_search_iterator_calc_buf_target(it, |
| 1246 |
it->buf_available + 1, |
| 1247 |
&target)) { |
| 1248 |
*gap_ret = true; |
| 1249 |
return NULL; |
| 1250 |
} |
| 1251 |
if (target > it->buf_capacity) { |
| 1252 |
size_t new_capacity = target; |
| 1253 |
if (new_capacity <= SIZE_MAX / 2) |
| 1254 |
new_capacity = next_power_of_two(new_capacity); |
| 1255 |
unsigned char *new_buf = realloc(it->buf, new_capacity); |
| 1256 |
if (!new_buf) |
| 1257 |
return &drgn_enomem; |
| 1258 |
it->buf = new_buf; |
| 1259 |
it->buf_capacity = new_capacity; |
| 1260 |
} |
| 1261 |
|
| 1262 |
while (it->buf_available < target) { |
| 1263 |
uint64_t address = it->buf_address + it->buf_available; |
| 1264 |
|
| 1265 |
auto tree_it = drgn_memory_segment_tree_search_le(tree, &address); |
| 1266 |
if (!tree_it.entry || tree_it.entry->max_address < address) { |
| 1267 |
// We encountered a gap in the address space. |
| 1268 |
*gap_ret = true; |
| 1269 |
return NULL; |
| 1270 |
} |
| 1271 |
|
| 1272 |
struct drgn_memory_segment *segment = tree_it.entry; |
| 1273 |
size_t n = target - it->buf_available; |
| 1274 |
if (n - 1 > segment->max_address - address) |
| 1275 |
n = segment->max_address - address + 1; |
| 1276 |
err = segment->read_fn(it->buf + it->buf_available, address, n, |
| 1277 |
address - segment->orig_min_address, |
| 1278 |
segment->arg, it->physical); |
| 1279 |
if (err) |
| 1280 |
return err; |
| 1281 |
it->buf_available += n; |
| 1282 |
} |
| 1283 |
*gap_ret = false; |
| 1284 |
return NULL; |
| 1285 |
} |
| 1286 |
|
| 1287 |
static struct drgn_error * |
| 1288 |
drgn_memory_search_iterator_next_regex(struct drgn_memory_search_iterator *it, |
| 1289 |
drgn_blocking_state *blocking_state, |
| 1290 |
uint64_t *addr_ret, |
| 1291 |
const void **match_ret, |
| 1292 |
size_t *match_len_ret) |
| 1293 |
{ |
| 1294 |
struct drgn_error *err; |
| 1295 |
|
| 1296 |
if (it->regex.need_refill) { |
| 1297 |
it->regex.next_match_options = 0; |
| 1298 |
bool gap; |
| 1299 |
err = drgn_memory_search_iterator_refill(it, blocking_state, |
| 1300 |
it->regex.min_length, |
| 1301 |
0, &gap); |
| 1302 |
if (err) |
| 1303 |
return err; |
| 1304 |
it->regex.partial_option = gap ? 0 : PCRE2_PARTIAL_HARD; |
| 1305 |
it->regex.need_refill = false; |
| 1306 |
} |
| 1307 |
|
| 1308 |
for (;;) { |
| 1309 |
uint32_t options = it->regex.partial_option |
| 1310 |
| it->regex.next_match_options; |
| 1311 |
if (it->buf_address != it->min_address) |
| 1312 |
options |= PCRE2_NOTBOL; |
| 1313 |
if (it->buf_address + it->buf_available - 1 < it->max_address) |
| 1314 |
options |= PCRE2_NOTEOL; |
| 1315 |
int rc = pcre2_match(it->regex.code, (PCRE2_SPTR)it->buf, |
| 1316 |
it->buf_available, it->pos, options, |
| 1317 |
it->regex.match_data, NULL); |
| 1318 |
if (rc == PCRE2_ERROR_NOMATCH) { |
| 1319 |
it->pos = it->buf_available; |
| 1320 |
it->regex.next_match_options = 0; |
| 1321 |
bool gap; |
| 1322 |
err = drgn_memory_search_iterator_refill(it, |
| 1323 |
blocking_state, |
| 1324 |
it->regex.min_length, |
| 1325 |
0, &gap); |
| 1326 |
if (err) |
| 1327 |
return err; |
| 1328 |
it->regex.partial_option = gap ? 0 : PCRE2_PARTIAL_HARD; |
| 1329 |
} else if (rc >= 0) { |
| 1330 |
PCRE2_SIZE *ovector = |
| 1331 |
pcre2_get_ovector_pointer(it->regex.match_data); |
| 1332 |
PCRE2_SIZE match_start = ovector[0]; |
| 1333 |
PCRE2_SIZE match_end = ovector[1]; |
| 1334 |
|
| 1335 |
if (addr_ret) { |
| 1336 |
*addr_ret = it->buf_address + match_start |
| 1337 |
+ it->address_offset; |
| 1338 |
} |
| 1339 |
if (match_ret) |
| 1340 |
*match_ret = it->buf + match_start; |
| 1341 |
if (match_len_ret) |
| 1342 |
*match_len_ret = match_end - match_start; |
| 1343 |
|
| 1344 |
PCRE2_SIZE next_pos; |
| 1345 |
if (drgn_pcre2_next_match(it->regex.match_data, |
| 1346 |
it->regex.utf8, it->buf, |
| 1347 |
it->buf_available, it->pos, |
| 1348 |
ovector, &next_pos, |
| 1349 |
&it->regex.next_match_options)) { |
| 1350 |
it->pos = next_pos; |
| 1351 |
} else { |
| 1352 |
it->pos = it->buf_available; |
| 1353 |
it->regex.need_refill = true; |
| 1354 |
} |
| 1355 |
return NULL; |
| 1356 |
} else if (rc == PCRE2_ERROR_PARTIAL) { |
| 1357 |
bool gap; |
| 1358 |
err = drgn_memory_search_iterator_try_extend(it, &gap); |
| 1359 |
if (err) |
| 1360 |
return err; |
| 1361 |
it->regex.partial_option = gap ? 0 : PCRE2_PARTIAL_HARD; |
| 1362 |
} else { |
| 1363 |
return drgn_error_pcre2(rc, NULL); |
| 1364 |
} |
| 1365 |
} |
| 1366 |
} |
| 1367 |
#endif |
| 1368 |
|
| 1369 |
LIBDRGN_PUBLIC struct drgn_error * |
| 1370 |
drgn_memory_search_iterator_next(struct drgn_memory_search_iterator *it, |
| 1371 |
uint64_t *addr_ret, const void **match_ret, |
| 1372 |
size_t *match_len_ret) |
| 1373 |
{ |
| 1374 |
struct drgn_error *err; |
| 1375 |
|
| 1376 |
drgn_blocking_guard(blocking_state); |
| 1377 |
|
| 1378 |
if (it->physical < 0) { |
| 1379 |
err = drgn_memory_search_iterator_set_address_range(it, 0, |
| 1380 |
UINT64_MAX, |
| 1381 |
false); |
| 1382 |
if (err) |
| 1383 |
return err; |
| 1384 |
} |
| 1385 |
|
| 1386 |
SWITCH_ENUM(it->mode) { |
| 1387 |
case DRGN_MEMORY_SEARCH_ITERATOR_MODE_MEMMEM: |
| 1388 |
return drgn_memory_search_iterator_next_memmem(it, |
| 1389 |
&blocking_state, |
| 1390 |
addr_ret, |
| 1391 |
match_ret, |
| 1392 |
match_len_ret); |
| 1393 |
#define X(bits) \ |
| 1394 |
case DRGN_MEMORY_SEARCH_ITERATOR_MODE_U##bits: \ |
| 1395 |
return drgn_memory_search_iterator_next_u##bits(it, \ |
| 1396 |
&blocking_state,\ |
| 1397 |
addr_ret, \ |
| 1398 |
match_ret, \ |
| 1399 |
match_len_ret); \ |
| 1400 |
case DRGN_MEMORY_SEARCH_ITERATOR_MODE_U##bits##_MULTI: \ |
| 1401 |
return drgn_memory_search_iterator_next_u##bits##_multi(it, \ |
| 1402 |
&blocking_state,\ |
| 1403 |
addr_ret,\ |
| 1404 |
match_ret,\ |
| 1405 |
match_len_ret); |
| 1406 |
SEARCH_MEMORY_UINT_SIZES |
| 1407 |
#undef X |
| 1408 |
#ifdef WITH_PCRE2 |
| 1409 |
case DRGN_MEMORY_SEARCH_ITERATOR_MODE_REGEX: |
| 1410 |
return drgn_memory_search_iterator_next_regex(it, |
| 1411 |
&blocking_state, |
| 1412 |
addr_ret, |
| 1413 |
match_ret, |
| 1414 |
match_len_ret); |
| 1415 |
#endif |
| 1416 |
default: |
| 1417 |
UNREACHABLE(); |
| 1418 |
} |
| 1419 |
} |
| 1420 |
|
| 1421 |
// This is a bit of a hack to work around Linux kernel address translation |
| 1422 |
// issues: if we're searching all memory or a specific range in the direct |
| 1423 |
// mapping, then do it as a physical memory search (but still return virtual |
| 1424 |
// addresses). |
| 1425 |
static struct drgn_error * |
| 1426 |
drgn_memory_search_iterator_replace_linux_kernel_address_range(struct drgn_memory_search_iterator *it) |
| 1427 |
{ |
| 1428 |
struct drgn_error *err; |
| 1429 |
|
| 1430 |
if (!(it->prog->flags & DRGN_PROGRAM_IS_LINUX_KERNEL) || it->physical) |
| 1431 |
return NULL; |
| 1432 |
|
| 1433 |
struct drgn_memory_segment_tree *tree = |
| 1434 |
&it->prog->reader.physical_segments; |
| 1435 |
if (drgn_memory_segment_tree_empty(tree)) |
| 1436 |
return NULL; |
| 1437 |
|
| 1438 |
uint64_t offset; |
| 1439 |
err = linux_helper_direct_mapping_offset(it->prog, &offset); |
| 1440 |
if (drgn_error_catch(&err, DRGN_ERROR_LOOKUP)) |
| 1441 |
return NULL; |
| 1442 |
else if (err) |
| 1443 |
return err; |
| 1444 |
|
| 1445 |
uint64_t address_mask = drgn_platform_address_mask(&it->prog->platform); |
| 1446 |
if (it->min_address == 0 && it->max_address == address_mask) { |
| 1447 |
it->address_offset = offset; |
| 1448 |
it->physical = true; |
| 1449 |
return NULL; |
| 1450 |
} |
| 1451 |
|
| 1452 |
auto first_it = drgn_memory_segment_tree_first(tree); |
| 1453 |
auto last_it = drgn_memory_segment_tree_last(tree); |
| 1454 |
if (first_it.entry->min_address <= it->min_address - offset |
| 1455 |
&& last_it.entry->max_address >= it->max_address - offset) { |
| 1456 |
it->min_address -= offset; |
| 1457 |
it->max_address -= offset; |
| 1458 |
it->address_offset = offset; |
| 1459 |
it->physical = true; |
| 1460 |
} |
| 1461 |
return NULL; |
| 1462 |
} |
| 1463 |
|
| 1464 |
LIBDRGN_PUBLIC struct drgn_error * |
| 1465 |
drgn_memory_search_iterator_set_address_range(struct drgn_memory_search_iterator *it, |
| 1466 |
uint64_t min_address, |
| 1467 |
uint64_t max_address, |
| 1468 |
bool physical) |
| 1469 |
{ |
| 1470 |
struct drgn_error *err; |
| 1471 |
|
| 1472 |
if (min_address > max_address) { |
| 1473 |
return drgn_error_create(DRGN_ERROR_INVALID_ARGUMENT, |
| 1474 |
"invalid memory search address range"); |
| 1475 |
} |
| 1476 |
|
| 1477 |
uint64_t address_mask; |
| 1478 |
err = drgn_program_address_mask(it->prog, &address_mask); |
| 1479 |
if (err) |
| 1480 |
return err; |
| 1481 |
if (max_address > address_mask) |
| 1482 |
max_address = address_mask; |
| 1483 |
|
| 1484 |
it->min_address = min_address; |
| 1485 |
it->max_address = max_address; |
| 1486 |
it->address_offset = 0; |
| 1487 |
it->physical = physical; |
| 1488 |
err = drgn_memory_search_iterator_replace_linux_kernel_address_range(it); |
| 1489 |
if (err) |
| 1490 |
return err; |
| 1491 |
|
| 1492 |
it->buf_available = 0; |
| 1493 |
it->pos = 0; |
| 1494 |
it->buf_address = it->min_address; |
| 1495 |
|
| 1496 |
#ifdef WITH_PCRE2 |
| 1497 |
if (it->mode == DRGN_MEMORY_SEARCH_ITERATOR_MODE_REGEX) |
| 1498 |
it->regex.need_refill = true; |
| 1499 |
#endif |
| 1500 |
|
| 1501 |
return NULL; |
| 1502 |
} |