kexec-tools: Add generic range code
This patch contains the core of the range handling code. All functions
operate on struct range which in this implementation is a sorted single
linked list. Scalability is not an issue here -> linked list.
Signed-off-by: Magnus Damm <[EMAIL PROTECTED]>
---
kexec/Makefile | 1
kexec/range.c | 248 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++
kexec/range.h | 32 +++++++
3 files changed, 281 insertions(+)
--- 0001/kexec/Makefile
+++ work/kexec/Makefile 2006-12-22 15:12:53.000000000 +0900
@@ -11,6 +11,7 @@ KCFLAGS:= $(CFLAGS) $(EXTRA_CFLAGS) -Ike
KEXEC_C_SRCS:= kexec/kexec.c
KEXEC_C_SRCS+= kexec/ifdown.c
+KEXEC_C_SRCS+= kexec/range.c
KEXEC_C_SRCS+= kexec/kexec-elf.c
KEXEC_C_SRCS+= kexec/kexec-elf-exec.c
KEXEC_C_SRCS+= kexec/kexec-elf-core.c
--- /dev/null
+++ work/kexec/range.c 2006-12-22 16:43:42.000000000 +0900
@@ -0,0 +1,248 @@
+#define _GNU_SOURCE
+#include <stdio.h>
+#include <stdarg.h>
+#include <string.h>
+#include <stdlib.h>
+#include <errno.h>
+#include <limits.h>
+#include <sys/types.h>
+#include <sys/stat.h>
+#include <unistd.h>
+#include <fcntl.h>
+#include "kexec.h"
+#include "crashdump.h"
+#include "range.h"
+
+/* private data structures and constants */
+
+struct range_link {
+ struct range_link *next;
+ unsigned long start;
+ unsigned long size;
+ int type;
+};
+
+#define MODE_SPACE 0
+#define MODE_OVERLAP 1
+#define MODE_INCLUDED 2
+#define MODE_INCLUDED_SPLIT 3
+
+int range_set(struct range *range,
+ unsigned long start, unsigned long size,
+ int type)
+{
+ struct range_link **p;
+ struct range_link *r = NULL;
+ struct range_link *r2;
+ struct range_link *new_links[2];
+ unsigned long tmp;
+ int k, n;
+ int mode = MODE_SPACE;
+
+ dfprintf(stdout, "inserting range %ld, %ld, %d\n", start, size, type);
+
+ /* find first overlapping link */
+
+ for (p = &range->first; *p; p = &(*p)->next) {
+ if (start > ((*p)->start + (*p)->size))
+ continue;
+
+ if ((start + size) > (*p)->start)
+ mode = MODE_OVERLAP;
+
+ if ((start >= (*p)->start)
+ && (start + size) <= ((*p)->start + (*p)->size))
+ mode = MODE_INCLUDED;
+
+ if ((start > (*p)->start)
+ && (start + size) < ((*p)->start + (*p)->size))
+ mode = MODE_INCLUDED_SPLIT;
+
+ r = *p;
+ break;
+ }
+
+ dfprintf(stdout, "mode = %d\n", mode);
+
+ if (mode != MODE_SPACE && type != RANGE_NOTHING && r->type == type) {
+
+ /* handle no-alloc merge case */
+
+ if (mode == MODE_INCLUDED || mode == MODE_INCLUDED_SPLIT) {
+ dfprintf(stdout, "range already set, nothing to do\n");
+ return 0;
+ }
+
+ /* expand existing link */
+
+ if (start < r->start) {
+ dfprintf(stdout, "merge mode, adjusting left\n");
+ r->size += r->start - start;
+ r->start = start;
+ }
+
+ if ((start + size) > (r->start + r->size)) {
+ dfprintf(stdout, "merge mode, adjusting right\n");
+ r->size = size + (start - r->start);
+ }
+
+ p = &r->next;
+ }
+ else {
+ /* allocate links first for easy error handling */
+
+ n = (type != RANGE_NOTHING) + (mode == MODE_INCLUDED_SPLIT);
+
+ for (k = 0; k < n; k++) {
+ r2 = malloc(sizeof(*r2));
+ if (!r2) {
+ while (k > 0) {
+ free(new_links[k - 1]);
+ k--;
+ }
+
+ dfprintf(stdout, "out of memory\n");
+ return -1;
+ }
+
+ memset(r2, 0, sizeof(*r2));
+ new_links[k] = r2;
+
+ dfprintf(stdout, "allocated link %d\n", k);
+ }
+
+ if (mode == MODE_INCLUDED_SPLIT) {
+ dfprintf(stdout, "INCLUDED_SPLIT, allocated link %d\n",
+ type != RANGE_NOTHING);
+
+ /* create a new link for the first part */
+
+ r2 = new_links[type != RANGE_NOTHING];
+
+ r2->start = r->start;
+ r2->size = start - r->start;
+ r2->type = r->type;
+ r2->next = *p;
+
+ dfprintf(stdout, "first new link is %ld, %ld, %d\n",
+ r2->start, r2->size, r2->type);
+
+ /* cut & merge code below handles the second link */
+
+ *p = r2;
+ p = &r2->next;
+ }
+
+ if ((mode == MODE_OVERLAP || mode == MODE_INCLUDED)
+ && r->start < start) {
+ dfprintf(stdout, "OVERLAP/INCLUDED, adjusting link\n");
+ r->size = start - r->start;
+ p = &r->next;
+ }
+
+ r = NULL;
+
+ if (type != RANGE_NOTHING) {
+ dfprintf(stdout, "using allocated link 0\n");
+
+ r = new_links[0];
+
+ r->start = start;
+ r->size = size;
+ r->type = type;
+ r->next = *p;
+ *p = r;
+
+ p = &r->next;
+ }
+ }
+
+ dfprintf(stdout, "(*p)->start = %ld\n", (*p) ? (*p)->start : -1);
+
+ /* remove links */
+
+ while (*p) {
+ tmp = (*p)->start + (*p)->size;
+
+ if ((start + size) <= tmp) {
+
+ /* cut or merge final partially overlapping link */
+
+ if ((start + size) < (*p)->start)
+ break;
+
+ if ((type != (*p)->type) || !r) {
+ dfprintf(stdout, "cutting final link %ld!\n",
+ (*p)->start);
+
+ (*p)->size = tmp - (start + size);
+ (*p)->start = start + size;
+
+ if ((*p)->size != 0)
+ break;
+ }
+ else {
+ dfprintf(stdout, "merging tail link %ld!\n",
+ (*p)->start);
+
+ r->size = tmp - r->start;
+ }
+ }
+
+ dfprintf(stdout, "removing link %ld!\n", (*p)->start);
+
+ r2 = (*p)->next;
+ free(*p);
+ *p = r2;
+ }
+
+ return 0;
+}
+
+int range_for_each(struct range *range,
+ int (*callback)(void *data,
+ int nr,
+ unsigned long start,
+ unsigned long size,
+ int type),
+ void *data)
+{
+ struct range_link *p;
+ int k = 0;
+ int ret = 0;
+
+ for (p = range->first; p; p = p->next) {
+
+ ret = callback(data, k, p->start, p->size, p->type);
+ if (ret < 0)
+ return ret;
+
+ k++;
+ }
+
+ return k;
+}
+
+static void range_dump_callback(void *data,
+ int nr,
+ unsigned long start,
+ unsigned long size,
+ int type)
+{
+ fprintf(stdout, "%d: %ld - %ld (%ld): %d\n",
+ nr, start, start + size - 1, size, type);
+}
+
+void range_dump(struct range *range, char *str)
+{
+ fprintf(stdout, "range_dump: %s\n", str);
+
+ range_for_each(range, range_dump_callback, NULL);
+
+ fprintf(stdout, "range_dump: %s - done\n", str);
+}
+
+void range_cleanup(struct range *range)
+{
+ range_set(range, 0, ~0, RANGE_NOTHING);
+}
--- /dev/null
+++ work/kexec/range.h 2006-12-22 15:12:54.000000000 +0900
@@ -0,0 +1,32 @@
+#ifndef RANGE_H
+#define RANGE_H
+
+struct range_link;
+
+struct range {
+ struct range_link *first;
+};
+
+#define RANGE_NOTHING 0
+
+static inline void range_init(struct range *range)
+{
+ range->first = NULL;
+}
+
+int range_set(struct range *range,
+ unsigned long start, unsigned long size,
+ int type);
+
+void range_dump(struct range *range, char *str);
+void range_cleanup(struct range *range);
+
+int range_for_each(struct range *range,
+ int (*callback)(void *data,
+ int nr,
+ unsigned long start,
+ unsigned long size,
+ int type),
+ void *data);
+
+#endif /* RANGE_H */
_______________________________________________
fastboot mailing list
fastboot@lists.osdl.org
https://lists.osdl.org/mailman/listinfo/fastboot
