Debian Codegraph @

libdrgn/memory_reader.c

raw
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 }