diff options
author | Andy Wingo <wingo@pobox.com> | 2013-11-09 15:51:54 +0100 |
---|---|---|
committer | Andy Wingo <wingo@pobox.com> | 2013-11-09 15:51:54 +0100 |
commit | 695e6b75515f87ec7ddca03d3d437bd8bf93130a (patch) | |
tree | 8f8b5c635afd70001a25c381b13fe6017636dcf1 | |
parent | 1b00f4c709016e6026e8baccf9d66f87d259c7a7 (diff) | |
download | guile-695e6b75515f87ec7ddca03d3d437bd8bf93130a.tar.gz |
Use binary search in find-elf-symbol
* module/system/vm/debug.scm (binary-search): New helper.
(find-elf-symbol): Use binary search.
-rw-r--r-- | module/system/vm/debug.scm | 42 |
1 files changed, 24 insertions, 18 deletions
diff --git a/module/system/vm/debug.scm b/module/system/vm/debug.scm index ca6fe07a0..17131b5e5 100644 --- a/module/system/vm/debug.scm +++ b/module/system/vm/debug.scm @@ -180,6 +180,17 @@ to have an ELF image if the program was defined in as a stub in C." (and=> (find-mapped-elf-image addr) debug-context-from-image)) +(define-inlinable (binary-search start end inc try failure) + (let lp ((start start) (end end)) + (if (eqv? start end) + (failure) + (let ((mid (+ start (* inc (floor/ (- end start) (* 2 inc)))))) + (try mid + (lambda () + (lp start mid)) + (lambda () + (lp (+ mid inc) end))))))) + (define (find-elf-symbol elf text-offset) "Search the symbol table of @var{elf} for the ELF symbol containing @var{text-offset}. @var{text-offset} is a byte offset in the text @@ -187,24 +198,19 @@ section of the ELF image. Returns an ELF symbol, or @code{#f}." (and=> (elf-section-by-name elf ".symtab") (lambda (symtab) - (let ((len (elf-symbol-table-len symtab)) - (strtab (elf-section elf (elf-section-link symtab)))) - ;; The symbols should be sorted, but maybe somehow that fails - ;; (for example if multiple objects are relinked together). So, - ;; a modicum of tolerance. - (define (bisect) - ;; FIXME: Implement. - #f) - (define (linear-search) - (let lp ((n 0)) - (and (< n len) - (let ((sym (elf-symbol-table-ref elf symtab n strtab))) - (if (and (<= (elf-symbol-value sym) text-offset) - (< text-offset (+ (elf-symbol-value sym) - (elf-symbol-size sym)))) - sym - (lp (1+ n))))))) - (or (bisect) (linear-search)))))) + (let ((strtab (elf-section elf (elf-section-link symtab)))) + (binary-search + 0 (elf-symbol-table-len symtab) 1 + (lambda (n continue-before continue-after) + (let* ((sym (elf-symbol-table-ref elf symtab n strtab)) + (val (elf-symbol-value sym)) + (size (elf-symbol-size sym))) + (cond + ((< text-offset val) (continue-before)) + ((<= (+ val size) text-offset) (continue-after)) + (else sym)))) + (lambda () + #f)))))) (define* (find-program-debug-info addr #:optional (context (find-debug-context addr))) |