{"id":6773,"date":"2012-08-24T07:00:00","date_gmt":"2012-08-24T07:00:00","guid":{"rendered":"https:\/\/blogs.msdn.microsoft.com\/oldnewthing\/2012\/08\/24\/dumping-a-hash-table-with-external-chaining-from-the-debugger\/"},"modified":"2012-08-24T07:00:00","modified_gmt":"2012-08-24T07:00:00","slug":"dumping-a-hash-table-with-external-chaining-from-the-debugger","status":"publish","type":"post","link":"https:\/\/devblogs.microsoft.com\/oldnewthing\/20120824-00\/?p=6773","title":{"rendered":"Dumping a hash table with external chaining from the debugger"},"content":{"rendered":"<p>\nI was doing some crash dump debugging, as I am often called upon to do,\nand one of the data structure I had to grovel through was something\nthat operated basically like an atom table, so that&#8217;s what I&#8217;ll call\nit.\nLike an atom table,\nit manages a collection of strings.\nYou can add a string to the table (getting a unique value back,\nwhich we will call an atom),\nand later you can hand it the atom and it will give you the string back.\nIt looked something like this:\n<\/p>\n<pre>\nstruct ENTRY\n{\n  ENTRY *next;\n  UINT   atom;\n  PCWSTR value;\n};\n#define ATOMTABLESIZE 19\nstruct ATOMTABLE\n{\n  ENTRY *buckets[ATOMTABLESIZE];\n};\n<\/pre>\n<p>\n(It didn&#8217;t actually look like this; I&#8217;ve reduced it to the smallest\nexample that still illustrates my point.)\n<\/p>\n<p>\nAs part of my debugging, I had an atom and needed to look it up\nin the table.\nA program would do this by simply calling the\n&#8220;here is an atom, please give me the string&#8221; function,\nbut since this was a crash dump,\nthere&#8217;s nothing around to execute anything.\n(Not that having a live machine would&#8217;ve made things much easier,\nbecause this was a kernel-mode crash,\nso you don&#8217;t get any of this edit-and-continue froofy stuff.\nThis is <i>real debugging<\/i>&trade;.)\n<\/p>\n<p>\nBut even though the crashed system can&#8217;t execute anything,\nthe <i>debugger<\/i> can execute stuff,\nand the debugger engine used by <code>kd<\/code>\ncomes with its own mini-programming language.\nHere&#8217;s how I dumped the atom table:\n<\/p>\n<pre>\n\/\/ note: this was entered all on one line\n\/\/ broken into two lines for readability\n0: kd&amp;gt .for (r $t0=0; @$t0 &lt; 0n19; r $t0=@$t0+1)\n         { dl poi (fffff8a0`06b69930+@$t0*8) 99 2 }\nfffff8a0`06ad3b90  fffff8a0`037a3fc0 fffff8a0`0000000c \\\nfffff8a0`037a3fc0  fffff8a0`037a4ae0 00000000`00000025 | $t0=0\nfffff8a0`037a4ae0  fffff8a0`02257580 00000000`00000036 |\nfffff8a0`02257580  00000000`00000000 00000000`00000056 \/\nfffff8a0`06ad3b30  fffff8a0`06ad3ad0 a9e8a9d8`0000000d \\\nfffff8a0`06ad3ad0  fffff8a0`037a4700 000007fc`0000000e |\nfffff8a0`037a4700  fffff8a0`01f96fb0 00000000`0000003f | $t0=1\nfffff8a0`01f96fb0  fffff8a0`06cfa5d0 fffff8a0`00000044 |\nfffff8a0`06cfa5d0  00000000`00000000 00181000`00000060 \/\nfffff8a0`033e7a70  fffff8a0`037a4770 00000020`00000023 \\\nfffff8a0`037a4770  fffff8a0`023b52f0 00000000`0000003e | $t0=2\nfffff8a0`023b52f0  fffff8a0`03b6e020 006f0063`00000059 |\nfffff8a0`03b6e020  00000000`00000000 00000000`00000075 \/\nfffff8a0`037a0670  fffff8a0`02b08870 fffff8a0`00000026 \\ $t0=3\nfffff8a0`03b9e390  00000000`00000000 00240000`00000071 \/\n...\n<\/pre>\n<p>\nLet&#8217;s take that weirdo command apart one piece at a time.\n<\/p>\n<p>\nThe overall command is\n<\/p>\n<pre>\n.for (a; b; c) { d }\n<\/pre>\n<p>\nThis operates the same as the C programming language.\n(<a HREF=\"http:\/\/blogs.msdn.com\/b\/oldnewthing\/archive\/2011\/05\/23\/10167156.aspx#10167462\">Sorry, Delphi programmers<\/a>,\nfor yet another C-centric example.)\nIn our case,\nwe use the <code>$t0<\/code> pseudo-register as our loop control.\n<\/p>\n<ul>\n<li><code>r $t0=0<\/code>\n    &mdash; this sets <code>$t0<\/code> to zero<\/p>\n<li><code>@$t0 &lt; 0n19<\/code>\n    &mdash; this stops once <code>$t0<\/code> reaches 19.<\/p>\n<li><code>r $t0=@$t0+1<\/code>\n    &mdash; this increments <code>$t0<\/code>.\n<\/ul>\n<p>\nNote that here as well as in the loop body, I prefix the register\nname with the <code>@<\/code> character when I want to obtain its value,\nin order to force it to be interpreted as a register.\n(Otherwise, the debugger will look for a symbol called <code>$t0<\/code>.)\n<\/p>\n<p>\nThe command being executed at each iteration is\n<code>{ dl poi (fffff8a0`06b69930+@$t0*8) 99 2 }<\/code>.\nLet&#8217;s break this down, too:\n<\/p>\n<ul>\n<li><code>dl<\/code>\n    &mdash; this command dumps a singly-linked list.<\/p>\n<li><code>poi (fffff8a0`06b69930+@$t0*8)<\/code>\n    &mdash; this is the head of the linked list.\n    In this example,\n    <code>0xfffff8a0`06b69930<\/code>\n    is the address of the <code>buckets<\/code> array,\n    so we add the loop counter times the size of a pointer (8, in\n    this case) to get the address of the <code>$t0<\/code>&#8216;th entry,\n    and then dereference it (<code>poi<\/code>) to get the address\n    of the head of the linked list.<\/p>\n<li><code>99<\/code>\n    &mdash; This is the maximum length of the linked list.\n    I picked an arbitrary large-enough number.\n    I like using 9&#8217;s because it carries the most value per keypress.\n    Other people like to use nice round numbers like <code>1000<\/code>,\n    but <code>999<\/code> saves you a whole keypress and is just one less.\n    (On the other hand, I don&#8217;t use <code>fff<\/code> because that runs\n    the risk of being misinterpreted as a symbol.)<\/p>\n<li><code>2<\/code>\n    &mdash;\n    This is the number of pointer-sized objects to dump at the start\n    of each node.\n    For 32-bit code, I use 4, whereas for 64-bit code, I use 2.\n    Why those values?\n    Because those are the maximum number of pointer-sized objects that\n    the debugger will print on one line.\n<\/ul>\n<p>\nOkay, so now I have that linked list dump.\nThe value I&#8217;m looking for is the <code>atom<\/code> whose value\nis <code>0x3F<\/code>, so I skim down the last column looking\nfor <code>0000003f<\/code>, and hey there it is.\n<\/p>\n<pre>\nfffff8a0`037a4700  fffff8a0`01f96fb0 00000000`<u>0000003f<\/u>\n<\/pre>\n<p>\nNow I have my <code>ENTRY<\/code>, and I can dump it to see what\nthe corresponding value is.\n<\/p>\n<pre>\n0: kd&gt; dt contoso!ENTRY fffff8a0`037a4700\n    +0x000 next: 0xfffff8a0`01f96fb0\n    +0x008 atom: 0x0000003f\n    +0x010 value: 0xffff8a0`01f97e20 -&gt; \"foo\"\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>I was doing some crash dump debugging, as I am often called upon to do, and one of the data structure I had to grovel through was something that operated basically like an atom table, so that&#8217;s what I&#8217;ll call it. Like an atom table, it manages a collection of strings. You can add a [&hellip;]<\/p>\n","protected":false},"author":1069,"featured_media":111744,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_acf_changed":false,"footnotes":""},"categories":[1],"tags":[26],"class_list":["post-6773","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-oldnewthing","tag-other"],"acf":[],"blog_post_summary":"<p>I was doing some crash dump debugging, as I am often called upon to do, and one of the data structure I had to grovel through was something that operated basically like an atom table, so that&#8217;s what I&#8217;ll call it. Like an atom table, it manages a collection of strings. You can add a [&hellip;]<\/p>\n","_links":{"self":[{"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/posts\/6773","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/users\/1069"}],"replies":[{"embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/comments?post=6773"}],"version-history":[{"count":0,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/posts\/6773\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/media\/111744"}],"wp:attachment":[{"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/media?parent=6773"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/categories?post=6773"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/tags?post=6773"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}