Edward O'Callaghan has uploaded this change for review.
search,Makefile: Import from CrOS verbatim
Change-Id: I7e4e90195b7857a4089d79264d471ede9ab79cd1
Signed-off-by: Edward O'Callaghan <quasisec@google.com>
---
M Makefile
A search.c
A search.h
3 files changed, 305 insertions(+), 1 deletion(-)
git pull ssh://review.coreboot.org:29418/flashrom refs/changes/61/47061/1
diff --git a/Makefile b/Makefile
index 225db9d..4f04ae9 100644
--- a/Makefile
+++ b/Makefile
@@ -643,7 +643,7 @@
###############################################################################
# Library code.
-LIB_OBJS = libflashrom.o layout.o flashrom.o udelay.o programmer.o helpers.o ich_descriptors.o fmap.o
+LIB_OBJS = libflashrom.o layout.o flashrom.o udelay.o programmer.o helpers.o ich_descriptors.o fmap.o search.o
###############################################################################
# Frontend related stuff.
diff --git a/search.c b/search.c
new file mode 100644
index 0000000..1a9f197
--- /dev/null
+++ b/search.c
@@ -0,0 +1,198 @@
+/*
+ * Copyright 2013, Google Inc.
+ * All rights reserved.
+ *
+ * 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.
+ * * Neither the name of Google Inc. nor the names of its
+ * contributors may be used to endorse or promote products derived from
+ * this software without specific prior written permission.
+ *
+ * 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.
+ *
+ * Alternatively, this software may be distributed under the terms of the
+ * GNU General Public License ("GPL") version 2 as published by the Free
+ * Software Foundation.
+ *
+ * This is ported from the flashmap utility: http://flashmap.googlecode.com
+ */
+
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include <limits.h>
+
+#include "flash.h"
+#include "search.h"
+
+
+/* Ceil a number to the minimum power of 2 value. For example,
+ * ceiling(2) = 2
+ * ceiling(5) = 8
+ * ceiling(254K) = 256K
+ *
+ * Return -1 if the input value is invalid..
+ */
+static long int ceiling(long int v) {
+ int shiftwidth;
+
+ if (v <= 0) return -1;
+
+ /* it is power of 2. */
+ if (!(v & (v - 1))) return v;
+
+ /* pollute all bits below MSB to 1. */
+ for (shiftwidth = (sizeof(v) * CHAR_BIT) / 2;
+ shiftwidth > 0;
+ shiftwidth /= 2) {
+ v = v | (v >> shiftwidth);
+ }
+
+ return v + 1;
+}
+
+int search_find_next(struct search_info *search, off_t *offsetp)
+{
+ int ret;
+
+ switch (search->state) {
+ case SEARCH_STATE_START:
+ search->ceiling_size = ceiling(search->total_size);
+ search->state = SEARCH_STATE_USE_HANDLER;
+ search->stride = search->ceiling_size / 2;
+ search->offset = search->ceiling_size - search->stride;
+ /* no break */
+ case SEARCH_STATE_USE_HANDLER:
+ search->state = SEARCH_STATE_BINARY_SEARCH;
+ search->offset = search->ceiling_size - search->stride;
+ if (search->handler) {
+ ret = search->handler(search, offsetp);
+ if (!ret &&
+ (*offsetp <
+ (search->total_size - search->min_size)) &&
+ (*offsetp >= 0))
+ return 0;
+ }
+ /* no break */
+ case SEARCH_STATE_BINARY_SEARCH:
+ /*
+ * For efficient operation, we start with the largest stride
+ * possible and then decrease the stride on each iteration. We
+ * will check for a remainder when modding the offset with the
+ * previous stride. This makes it so that each offset is only
+ * checked once.
+ *
+ * At some point, programmer transaction overhead becomes
+ * greater than simply copying everything into RAM and
+ * checking one byte at a time. At some arbitrary point, we'll
+ * stop being clever and use brute force instead by copying
+ * the while ROM into RAM and searching one byte at a time.
+ *
+ * In practice, the flash map is usually stored in a
+ * write-protected section of flash which is often at the top
+ * of ROM where the boot vector on x86 resides. Because of
+ * this, we will search from top to bottom.
+ *
+ * We assume we can always return at least one offset here.
+ */
+ *offsetp = search->offset;
+
+ /*
+ * OK, now what offset should we return next? This loop skips
+ * any offsets that were already checked by larger strides.
+ */
+ do {
+ search->offset -= search->stride;
+ } while (search->offset % (search->stride * 2) == 0);
+
+ /* Move to next stride if necessary */
+ if (search->offset < 0) {
+ search->stride /= 2;
+ search->offset = search->ceiling_size - search->stride;
+ while (search->offset >
+ (search->total_size - search->min_size))
+ search->offset -= search->stride;
+ if (search->stride < 16) {
+ search->state = SEARCH_STATE_FULL_SEARCH;
+ search->offset = search->total_size - 1;
+ search->image = malloc(search->total_size);
+ if (!search->image) {
+ msg_gdbg("%s: failed to allocate %zd "
+ "bytes for search->image",
+ __func__, search->total_size);
+ return -1;
+ }
+ if (search->read_chunk(search->source_handle,
+ search->image,
+ 0, search->total_size)) {
+ msg_gdbg("[L%d] failed to read flash contents\n",
+ __LINE__);
+ return -1;
+ }
+ msg_gdbg("using brute force method to find fmap\n");
+ }
+ }
+ return 0;
+ case SEARCH_STATE_FULL_SEARCH:
+ /*
+ * brute force
+ * We have read the entire ROM above, so the caller will be
+ * able to use search->image to access it.
+ *
+ * FIXME: This results in the entire ROM being read twice --
+ * once here and again in doit(). The performance penalty
+ * needs to be dealt with before going upstream.
+ */
+ do {
+ *offsetp = search->offset--;
+ } while (*offsetp > search->total_size - search->min_size);
+ if (search->offset < 0)
+ search->state = SEARCH_STATE_DONE;
+ return 0;
+ case SEARCH_STATE_DONE:
+ break;
+ }
+
+ /* Give up, it is not there */
+ return -1;
+}
+
+void search_init(struct search_info *search,
+ void *source_handle,
+ size_t image_size,
+ size_t min_size,
+ int (*read_chunk)(void *handle,
+ void *dest,
+ size_t offset,
+ size_t size))
+{
+ memset(search, '\0', sizeof(*search));
+ search->min_size = min_size;
+ search->total_size = image_size;
+ search->source_handle = source_handle;
+ search->read_chunk = read_chunk;
+}
+
+void search_free(struct search_info *search)
+{
+ if (search->image)
+ free(search->image);
+}
diff --git a/search.h b/search.h
new file mode 100644
index 0000000..a1a5ac8
--- /dev/null
+++ b/search.h
@@ -0,0 +1,106 @@
+/*
+ * Copyright 2013, Google Inc.
+ * All rights reserved.
+ *
+ * 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.
+ * * Neither the name of Google Inc. nor the names of its
+ * contributors may be used to endorse or promote products derived from
+ * this software without specific prior written permission.
+ *
+ * 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.
+ *
+ * Alternatively, this software may be distributed under the terms of the
+ * GNU General Public License ("GPL") version 2 as published by the Free
+ * Software Foundation.
+ *
+ * This is ported from the flashmap utility: http://flashmap.googlecode.com
+ */
+
+#ifndef FLASHMAP_LIB_SEARCH_H__
+#define FLASHMAP_LIB_SEARCH_H__
+
+/* Our current state in the search process */
+enum search_state_t {
+ SEARCH_STATE_START,
+ SEARCH_STATE_USE_HANDLER, /* Call handler function */
+ SEARCH_STATE_BINARY_SEARCH, /* Fast binary search */
+ SEARCH_STATE_FULL_SEARCH, /* Slow incremental search */
+ SEARCH_STATE_DONE, /* Search completed */
+};
+
+/* Keeps track of the state of our search */
+struct search_info {
+ void *source_handle; /* Pointer for read_chunk() below. */
+ int (*read_chunk)(void *handle, /* Callback to read chunk of data. */
+ void *dest, size_t offset, size_t size);
+ size_t total_size; /* Total size of the flash chip. */
+ enum search_state_t state; /* Current state */
+ size_t ceiling_size; /* Lowest power of 2 >= flash size */
+ size_t stride; /* Current binary search stride */
+ off_t offset; /* Next offset to return */
+ uint8_t *image; /* Cache of entire flash image */
+ size_t min_size; /* Minimum size of data to find */
+ /*
+ * Utility wrapper for using external programs to aid in our search.
+ * @search: Pointer to search information
+ * @offset: Wrapper will set this if successful
+ *
+ * @return 0 if successful, -1 to indicate failure or offset not
+ * found by utility
+ */
+ int (*handler)(struct search_info *search, off_t *offset);
+};
+
+/**
+ * search_find_next() - Find the next offset to check in a search operation
+ *
+ * If search->image is not NULL, then it contains the full flash image and
+ * the caller can use this instead of reading the data again.
+ *
+ * @search: Search information, set up by search_init()
+ * @offsetp: Returns next offset to check
+ * @return 0 if we have an offset, -1 if we have run out of places to look
+ */
+int search_find_next(struct search_info *search, off_t *offsetp);
+
+/** search_init() - Get ready to start a search
+ *
+ * @search: Search information, set up by this function
+ * @flash: Information about the flash chip
+ * @min_size: Minimum size of region that we want to find
+ */
+void search_init(struct search_info *search,
+ void *source_handle,
+ size_t image_size,
+ size_t min_size,
+ int (*read_chunk)(void *handle,
+ void *dest,
+ size_t offset,
+ size_t size));
+
+/** search_free() - Free memory allocated by search
+ *
+ * @search: Search information, set up by search_init()
+ */
+void search_free(struct search_info *search);
+
+#endif
To view, visit change 47061. To unsubscribe, or for help writing mail filters, visit settings.