Edward O'Callaghan has uploaded this change for review. ( https://review.coreboot.org/c/flashrom/+/47061 )
Change subject: search,Makefile: Import from CrOS verbatim ......................................................................
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