From nobody Mon Feb 9 19:54:20 2026 Delivered-To: importer@patchew.org Received-SPF: pass (zoho.com: domain of gnu.org designates 208.118.235.17 as permitted sender) client-ip=208.118.235.17; envelope-from=qemu-devel-bounces+importer=patchew.org@nongnu.org; helo=lists.gnu.org; Authentication-Results: mx.zohomail.com; spf=pass (zoho.com: domain of gnu.org designates 208.118.235.17 as permitted sender) smtp.mailfrom=qemu-devel-bounces+importer=patchew.org@nongnu.org Return-Path: Received: from lists.gnu.org (lists.gnu.org [208.118.235.17]) by mx.zohomail.com with SMTPS id 1543503226435448.85489156866345; Thu, 29 Nov 2018 06:53:46 -0800 (PST) Received: from localhost ([::1]:54585 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1gSNhJ-0003Uq-CS for importer@patchew.org; Thu, 29 Nov 2018 09:53:45 -0500 Received: from eggs.gnu.org ([2001:4830:134:3::10]:52768) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1gSNIy-0004aV-RE for qemu-devel@nongnu.org; Thu, 29 Nov 2018 09:28:37 -0500 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1gSNIx-0005qI-UR for qemu-devel@nongnu.org; Thu, 29 Nov 2018 09:28:36 -0500 Received: from mail.ispras.ru ([83.149.199.45]:39382) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1gSNIx-0005p9-GL for qemu-devel@nongnu.org; Thu, 29 Nov 2018 09:28:35 -0500 Received: from Misha-PC.lan02.inno (unknown [85.142.117.226]) by mail.ispras.ru (Postfix) with ESMTPSA id B9CA75400DC; Thu, 29 Nov 2018 17:28:34 +0300 (MSK) From: Mikhail Abakumov To: qemu-devel@nongnu.org Date: Thu, 29 Nov 2018 17:28:32 +0300 Message-ID: <154350171209.8036.6955133809742280150.stgit@Misha-PC.lan02.inno> In-Reply-To: <154350164526.8036.12623669071583857903.stgit@Misha-PC.lan02.inno> References: <154350164526.8036.12623669071583857903.stgit@Misha-PC.lan02.inno> User-Agent: StGit/0.17.1-dirty MIME-Version: 1.0 Content-Type: text/plain; charset="utf-8" Content-Transfer-Encoding: quoted-printable X-detected-operating-system: by eggs.gnu.org: GNU/Linux 3.x [fuzzy] X-Received-From: 83.149.199.45 Subject: [Qemu-devel] [PATCH 11/39] windbg: add windbg_search_vmaddr X-BeenThere: qemu-devel@nongnu.org X-Mailman-Version: 2.1.21 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Cc: sw@weilnetz.de, lprosek@redhat.com, dovgaluk@ispras.ru, rkagan@virtuozzo.com, pbonzini@redhat.com, den@openvz.org Errors-To: qemu-devel-bounces+importer=patchew.org@nongnu.org Sender: "Qemu-devel" Add function to search in virtual memory. Implemented Boyer-Moore search algorithm. Signed-off-by: Mikhail Abakumov Signed-off-by: Pavel Dovgalyuk --- include/exec/windbgstub-utils.h | 4 + windbgstub-utils.c | 117 +++++++++++++++++++++++++++++++++++= ++++ 2 files changed, 121 insertions(+) diff --git a/include/exec/windbgstub-utils.h b/include/exec/windbgstub-util= s.h index e076227b39..2760684cfb 100644 --- a/include/exec/windbgstub-utils.h +++ b/include/exec/windbgstub-utils.h @@ -59,4 +59,8 @@ const char *kd_pkt_type_name(int id); bool windbg_on_load(void); void windbg_on_reset(void); =20 +InitedAddr windbg_search_vmaddr(CPUState *cs, target_ulong start, + target_ulong finish, const uint8_t *patter= n, + int pLen); + #endif /* WINDBGSTUB_UTILS_H */ diff --git a/windbgstub-utils.c b/windbgstub-utils.c index 968e5cb2dd..dce82987bb 100644 --- a/windbgstub-utils.c +++ b/windbgstub-utils.c @@ -80,6 +80,123 @@ static const char *kd_packet_type_names[] =3D { "PACKET_TYPE_MAX", }; =20 +static void prep_bmbc(const uint8_t *pattern, int pLen, int bmBc[]) +{ + int i; + + for (i =3D 0; i < 256; ++i) { + bmBc[i] =3D pLen; + } + for (i =3D 0; i < pLen - 1; ++i) { + bmBc[pattern[i]] =3D pLen - i - 1; + } +} + +static void prep_suffixes(const uint8_t *pattern, int pLen, int *suff) +{ + int f, g, i; + + suff[pLen - 1] =3D pLen; + f =3D 0; + g =3D pLen - 1; + for (i =3D pLen - 2; i >=3D 0; --i) { + if (i > g && suff[i + pLen - 1 - f] < i - g) { + suff[i] =3D suff[i + pLen - 1 - f]; + } else { + if (i < g) { + g =3D i; + } + f =3D i; + while (g >=3D 0 && pattern[g] =3D=3D pattern[g + pLen - 1 - f]= ) { + --g; + } + suff[i] =3D f - g; + } + } +} + +static void prep_bmgs(const uint8_t *pattern, int pLen, int bmGs[]) +{ + int i, j, suff[pLen]; + + prep_suffixes(pattern, pLen, suff); + + for (i =3D 0; i < pLen; ++i) { + bmGs[i] =3D pLen; + } + + j =3D 0; + for (i =3D pLen - 1; i >=3D 0; --i) { + if (suff[i] =3D=3D i + 1) { + for (; j < pLen - 1 - i; ++j) { + if (bmGs[j] =3D=3D pLen) { + bmGs[j] =3D pLen - 1 - i; + } + } + } + } + + for (i =3D 0; i <=3D pLen - 2; ++i) { + bmGs[pLen - 1 - suff[i]] =3D pLen - 1 - i; + } +} + +static int search_boyermoore(const uint8_t *data, int dLen, + const uint8_t *pattern, int pLen, int bmGs[], + int bmBc[]) +{ + int i; + int j =3D 0; + while (j <=3D dLen - pLen) { + i =3D pLen - 1; + while (i >=3D 0 && pattern[i] =3D=3D data[i + j]) { + --i; + } + if (i < 0) { + return j; + } else { + j +=3D MAX(bmGs[i], bmBc[data[i + j]] - pLen + 1 + i); + } + } + return -1; +} + +InitedAddr windbg_search_vmaddr(CPUState *cs, target_ulong start, + target_ulong finish, const uint8_t *patter= n, + int pLen) +{ + InitedAddr ret; + int bmGs[pLen], bmBc[256]; + int find; + target_ulong offset =3D start; + target_ulong step =3D MIN(MAX(finish - start, 0x10000), pLen * 2); + + if (finish <=3D start || pLen > finish - start) { + return ret; + } + + uint8_t *buf =3D g_new(uint8_t, step); + + prep_bmgs(pattern, pLen, bmGs); + prep_bmbc(pattern, pLen, bmBc); + + while (offset < finish) { + step =3D MIN(step, finish - offset); + if (cpu_memory_rw_debug(cs, offset, buf, step, 0) =3D=3D 0) { + find =3D search_boyermoore(buf, step, pattern, pLen, bmGs, bmB= c); + if (find >=3D 0) { + ret.addr =3D offset + find; + ret.is_init =3D true; + break; + } + } + offset +=3D step - pLen; + } + + g_free(buf); + return ret; +} + const char *kd_api_name(int id) { return (id >=3D DbgKdMinimumManipulate && id < DbgKdMaximumManipulate)