diff options
author | H. Peter Anvin <hpa@zytor.com> | 2010-06-21 22:59:19 -0700 |
---|---|---|
committer | H. Peter Anvin <hpa@zytor.com> | 2010-06-21 22:59:19 -0700 |
commit | e928919b5b58b518e15afaff92c319b2b832dbc8 (patch) | |
tree | 593e92813dca317d7ce86e784b5126fdb6e47d9e /com32/sysdump | |
parent | a4f0785b84f3d8fc047c4eb29d139d0d1c7b9704 (diff) | |
download | syslinux-e928919b5b58b518e15afaff92c319b2b832dbc8.tar.gz |
sysdump: smarter ACPI dump
Follow the XSDT as well as the RSDT, at least as long as we can do
that with 32-bit addresses. Actually keep track of what we have
already dumped.
Signed-off-by: H. Peter Anvin <hpa@zytor.com>
Diffstat (limited to 'com32/sysdump')
-rw-r--r-- | com32/sysdump/acpi.c | 122 | ||||
-rw-r--r-- | com32/sysdump/rbtree.c | 132 | ||||
-rw-r--r-- | com32/sysdump/rbtree.h | 53 |
3 files changed, 288 insertions, 19 deletions
diff --git a/com32/sysdump/acpi.c b/com32/sysdump/acpi.c index 48b890ae..8671fc8a 100644 --- a/com32/sysdump/acpi.c +++ b/com32/sysdump/acpi.c @@ -19,6 +19,7 @@ #include <stdlib.h> #include "sysdump.h" #include "backend.h" +#include "rbtree.h" struct acpi_rsdp { uint8_t magic[8]; /* "RSD PTR " */ @@ -27,7 +28,7 @@ struct acpi_rsdp { uint8_t rev; uint32_t rsdt_addr; uint32_t len; - uint64_t xdst_addr; + uint64_t xsdt_addr; uint8_t xcsum; uint8_t rsvd[3]; }; @@ -49,6 +50,35 @@ struct acpi_rsdt { uint32_t entry[0]; }; +struct acpi_xsdt { + struct acpi_hdr hdr; + uint64_t entry[0]; +}; + +static struct rbtree *rb_types, *rb_addrs; + +static bool rb_has(struct rbtree **tree, uint64_t key) +{ + struct rbtree *node; + + node = rb_search(*tree, key); + if (node && node->key == key) + return true; + + node = malloc(sizeof *node); + if (node) { + node->key = key; + *tree = rb_insert(*tree, node); + } + return false; +} + +static inline bool addr_ok(uint64_t addr) +{ + /* We can only handle 32-bit addresses for now... */ + return addr <= 0xffffffff; +} + enum tbl_errs { ERR_NONE, /* No errors */ ERR_CSUM, /* Invalid checksum */ @@ -125,10 +155,15 @@ static void dump_table(struct backend *be, const char name[], const void *ptr, uint32_t len) { char namebuf[64]; + uint32_t name_key = *(uint32_t *)name; - /* XXX: this make cause the same directory to show up more than once */ - snprintf(namebuf, sizeof namebuf, "acpi/%4.4s", name); - cpio_mkdir(be, namebuf); + if (rb_has(&rb_addrs, (size_t)ptr)) + return; /* Already dumped this table */ + + if (!rb_has(&rb_types, name_key)) { + snprintf(namebuf, sizeof namebuf, "acpi/%4.4s", name); + cpio_mkdir(be, namebuf); + } snprintf(namebuf, sizeof namebuf, "acpi/%4.4s/%08x", name, (uint32_t)ptr); cpio_hdr(be, MODE_FILE, len, namebuf); @@ -136,27 +171,14 @@ static void dump_table(struct backend *be, write_data(be, ptr, len); } -void dump_acpi(struct backend *be) +static void dump_rsdt(struct backend *be, const struct acpi_rsdp *rsdp) { - const struct acpi_rsdp *rsdp; const struct acpi_rsdt *rsdt; - uint32_t rsdp_len; uint32_t i, n; - rsdp = find_rsdp(); - - if (!rsdp) - return; /* No ACPI information found */ - - cpio_mkdir(be, "acpi"); - - rsdp_len = rsdp->rev > 0 ? rsdp->len : 20; - - dump_table(be, "RSDP", rsdp, rsdp_len); - rsdt = (const struct acpi_rsdt *)rsdp->rsdt_addr; - if (memcmp(rsdt->hdr.sig, "RSDT", 4) || is_valid_table(rsdt) != ERR_NONE) + if (memcmp(rsdt->hdr.sig, "RSDT", 4) || is_valid_table(rsdt) > ERR_CSUM) return; dump_table(be, rsdt->hdr.sig, rsdt, rsdt->hdr.len); @@ -173,3 +195,65 @@ void dump_acpi(struct backend *be) dump_table(be, hdr->sig, hdr, hdr->len); } } + +static void dump_xsdt(struct backend *be, const struct acpi_rsdp *rsdp) +{ + const struct acpi_xsdt *xsdt; + uint32_t rsdp_len = rsdp->rev > 0 ? rsdp->len : 20; + uint32_t i, n; + + if (rsdp_len < 34) + return; + + if (!addr_ok(rsdp->xsdt_addr)) + return; + + xsdt = (const struct acpi_xsdt *)(size_t)rsdp->xsdt_addr; + + if (memcmp(xsdt->hdr.sig, "XSDT", 4) || is_valid_table(xsdt) > ERR_CSUM) + return; + + dump_table(be, xsdt->hdr.sig, xsdt, xsdt->hdr.len); + + if (xsdt->hdr.len < 36) + return; + + n = (xsdt->hdr.len - 36) >> 3; + + for (i = 0; i < n; i++) { + const struct acpi_hdr *hdr; + if (addr_ok(xsdt->entry[i])) { + hdr = (const struct acpi_hdr *)(size_t)(xsdt->entry[i]); + + if (is_valid_table(hdr) <= ERR_CSUM) + dump_table(be, hdr->sig, hdr, hdr->len); + } + } +} + +void dump_acpi(struct backend *be) +{ + const struct acpi_rsdp *rsdp; + uint32_t rsdp_len; + + rsdp = find_rsdp(); + + printf("Dumping ACPI... "); + + if (!rsdp) + return; /* No ACPI information found */ + + cpio_mkdir(be, "acpi"); + + rsdp_len = rsdp->rev > 0 ? rsdp->len : 20; + + dump_table(be, "RSDP", rsdp, rsdp_len); + + dump_rsdt(be, rsdp); + dump_xsdt(be, rsdp); + + rb_destroy(rb_types); + rb_destroy(rb_addrs); + + printf("done.\n"); +} diff --git a/com32/sysdump/rbtree.c b/com32/sysdump/rbtree.c new file mode 100644 index 00000000..1d10e098 --- /dev/null +++ b/com32/sysdump/rbtree.c @@ -0,0 +1,132 @@ +/* ----------------------------------------------------------------------- * + * + * Copyright 1996-2009 The NASM Authors - All Rights Reserved + * See the file AUTHORS included with the NASM distribution for + * the specific copyright holders. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following + * conditions are met: + * + * * Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * * Redistributions in binary form must reproduce the above + * copyright notice, this list of conditions and the following + * disclaimer in the documentation and/or other materials provided + * with the distribution. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND + * CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, + * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF + * MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE + * DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR + * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, + * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT + * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; + * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) + * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN + * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR + * OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, + * EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + * + * ----------------------------------------------------------------------- */ + +/* + * rbtree.c + * + * Simple implementation of a left-leaning red-black tree with 64-bit + * integer keys. The search operation will return the highest node <= + * the key; only search and insert are supported, but additional + * standard llrbtree operations can be coded up at will. + * + * See http://www.cs.princeton.edu/~rs/talks/LLRB/RedBlack.pdf for + * information about left-leaning red-black trees. + */ + +#include <stdlib.h> +#include "rbtree.h" + +struct rbtree *rb_search(struct rbtree *tree, uint64_t key) +{ + struct rbtree *best = NULL; + + while (tree) { + if (tree->key == key) + return tree; + else if (tree->key > key) + tree = tree->left; + else { + best = tree; + tree = tree->right; + } + } + return best; +} + +static bool is_red(struct rbtree *h) +{ + return h && h->red; +} + +static struct rbtree *rotate_left(struct rbtree *h) +{ + struct rbtree *x = h->right; + h->right = x->left; + x->left = h; + x->red = x->left->red; + x->left->red = true; + return x; +} + +static struct rbtree *rotate_right(struct rbtree *h) +{ + struct rbtree *x = h->left; + h->left = x->right; + x->right = h; + x->red = x->right->red; + x->right->red = true; + return x; +} + +static void color_flip(struct rbtree *h) +{ + h->red = !h->red; + h->left->red = !h->left->red; + h->right->red = !h->right->red; +} + +struct rbtree *rb_insert(struct rbtree *tree, struct rbtree *node) +{ + node->left = node->right = NULL; + node->red = false; + + if (!tree) { + node->red = true; + return node; + } + + if (is_red(tree->left) && is_red(tree->right)) + color_flip(tree); + + if (node->key < tree->key) + tree->left = rb_insert(tree->left, node); + else + tree->right = rb_insert(tree->right, node); + + if (is_red(tree->right)) + tree = rotate_left(tree); + + if (is_red(tree->left) && is_red(tree->left->left)) + tree = rotate_right(tree); + + return tree; +} + +void rb_destroy(struct rbtree *tree) +{ + if (tree->left) + rb_destroy(tree->left); + if (tree->right) + rb_destroy(tree->right); + free(tree); +} diff --git a/com32/sysdump/rbtree.h b/com32/sysdump/rbtree.h new file mode 100644 index 00000000..dcdcd6ba --- /dev/null +++ b/com32/sysdump/rbtree.h @@ -0,0 +1,53 @@ +/* ----------------------------------------------------------------------- * + * + * Copyright 1996-2009 The NASM Authors - All Rights Reserved + * See the file AUTHORS included with the NASM distribution for + * the specific copyright holders. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following + * conditions are met: + * + * * Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * * Redistributions in binary form must reproduce the above + * copyright notice, this list of conditions and the following + * disclaimer in the documentation and/or other materials provided + * with the distribution. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND + * CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, + * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF + * MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE + * DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR + * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, + * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT + * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; + * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) + * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN + * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR + * OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, + * EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + * + * ----------------------------------------------------------------------- */ + +#ifndef NASM_RBTREE_H +#define NASM_RBTREE_H + +#include <inttypes.h> +#include <stdbool.h> + +/* This structure should be embedded in a larger data structure; + the final output from rb_search() can then be converted back + to the larger data structure via container_of(). */ +struct rbtree { + uint64_t key; + struct rbtree *left, *right; + bool red; +}; + +struct rbtree *rb_insert(struct rbtree *, struct rbtree *); +struct rbtree *rb_search(struct rbtree *, uint64_t); +void rb_destroy(struct rbtree *); + +#endif /* NASM_RBTREE_H */ |