This is the mail archive of the
cluster-cvs@sourceware.org
mailing list for the cluster.
RHEL5 - clogd/dm-log-clustered: Code clean-up/stream-lining
- From: Jonathan Brassow <jbrassow at fedoraproject dot org>
- To: cluster-cvs-relay at redhat dot com
- Date: Tue, 28 Oct 2008 15:18:15 +0000 (UTC)
- Subject: RHEL5 - clogd/dm-log-clustered: Code clean-up/stream-lining
Gitweb: http://git.fedorahosted.org/git/cluster.git?p=cluster.git;a=commitdiff;h=ae8bd1b0fe749b8c4af6de77b423c9be3c3653e9
Commit: ae8bd1b0fe749b8c4af6de77b423c9be3c3653e9
Parent: cc5877e65fad20dd8657881a7ca7361e6e4c08bf
Author: Jonathan Brassow <jbrassow@redhat.com>
AuthorDate: Mon Oct 27 11:45:22 2008 -0500
Committer: Jonathan Brassow <jbrassow@redhat.com>
CommitterDate: Tue Oct 28 10:16:45 2008 -0500
clogd/dm-log-clustered: Code clean-up/stream-lining
Get rid of some unnecessary files:
Don't need these copies anymore since they are exposed by the kernel now.
- cmirror-kernel/src/dm-log.h-copy
- cmirror-kernel/src/dm.h-copy
Since we are not using multiple threads in clogd, we can get rid of
some of the more complicated structures.
- cmirror/src/queues.c
- cmirror/src/queues.h
- cmirror/src/rbtree.c
- cmirror/src/rbtree.h
---
cmirror-kernel/src/dm-log.h-copy | 163 -----------
cmirror-kernel/src/dm.h-copy | 149 ----------
cmirror/src/Makefile | 2 +-
cmirror/src/clogd.c | 13 +-
cmirror/src/cluster.c | 568 +++++++++++++-------------------------
cmirror/src/functions.c | 11 +-
cmirror/src/local.c | 74 ++----
cmirror/src/queues.c | 239 ----------------
cmirror/src/queues.h | 30 --
cmirror/src/rbtree.c | 479 --------------------------------
cmirror/src/rbtree.h | 64 -----
11 files changed, 224 insertions(+), 1568 deletions(-)
diff --git a/cmirror-kernel/src/dm-log.h-copy b/cmirror-kernel/src/dm-log.h-copy
deleted file mode 100644
index 414d110..0000000
--- a/cmirror-kernel/src/dm-log.h-copy
+++ /dev/null
@@ -1,163 +0,0 @@
-/*
- * Copyright (C) 2003 Sistina Software
- *
- * This file is released under the LGPL.
- */
-
-#ifndef DM_DIRTY_LOG
-#define DM_DIRTY_LOG
-
-#include "dm.h"
-
-/*
- * Values returned by get_failure_response()
- * DMLOG_IOERR_IGNORE: ignore device failures
- * DMLOG_IOERR_BLOCK: issue dm event, and do not complete
- * I/O until presuspend is recieved.
- */
-#define DMLOG_IOERR_IGNORE 0
-#define DMLOG_IOERR_BLOCK 1
-
-typedef sector_t region_t;
-
-struct dirty_log_type;
-
-struct dirty_log {
- struct dirty_log_type *type;
- void *context;
-};
-
-struct dirty_log_type {
- uint64_t features;
- struct list_head list;
- const char *name;
- struct module *module;
- unsigned int use_count;
- unsigned int flags;
-
- int (*ctr)(struct dirty_log *log, struct dm_target *ti,
- unsigned int argc, char **argv);
- void (*dtr)(struct dirty_log *log);
-
- /*
- * There are times when we don't want the log to touch
- * the disk.
- */
- int (*presuspend)(struct dirty_log *log);
- int (*postsuspend)(struct dirty_log *log);
- int (*resume)(struct dirty_log *log);
-
- /*
- * Retrieves the smallest size of region that the log can
- * deal with.
- */
- uint32_t (*get_region_size)(struct dirty_log *log);
-
- /*
- * A predicate to say whether a region is clean or not.
- * May block.
- */
- int (*is_clean)(struct dirty_log *log, region_t region);
-
- /*
- * Returns: 0, 1, -EWOULDBLOCK, < 0
- *
- * A predicate function to check the area given by
- * [sector, sector + len) is in sync.
- *
- * If -EWOULDBLOCK is returned the state of the region is
- * unknown, typically this will result in a read being
- * passed to a daemon to deal with, since a daemon is
- * allowed to block.
- */
- int (*in_sync)(struct dirty_log *log, region_t region, int can_block);
-
- /*
- * Flush the current log state (eg, to disk). This
- * function may block.
- */
- int (*flush)(struct dirty_log *log);
-
- /*
- * Mark an area as clean or dirty. These functions may
- * block, though for performance reasons blocking should
- * be extremely rare (eg, allocating another chunk of
- * memory for some reason).
- *
- * clear_region will only clear the region if it
- * is also in-sync.
- */
- void (*mark_region)(struct dirty_log *log, region_t region);
- void (*clear_region)(struct dirty_log *log, region_t region);
-
- /*
- * Returns: <0 (error), 0 (no region), 1 (region)
- *
- * The mirrord will need perform recovery on regions of
- * the mirror that are in the NOSYNC state. This
- * function asks the log to tell the caller about the
- * next region that this machine should recover.
- *
- * Do not confuse this function with 'in_sync()', one
- * tells you if an area is synchronised, the other
- * assigns recovery work.
- */
- int (*get_resync_work)(struct dirty_log *log, region_t *region);
-
- /*
- * This notifies the log that the resync status of a region
- * has changed. It also clears the region from the recovering
- * list (if present).
- */
- void (*set_region_sync)(struct dirty_log *log,
- region_t region, int in_sync);
-
- /*
- * Returns the number of regions that are in sync.
- */
- region_t (*get_sync_count)(struct dirty_log *log);
-
- /*
- * Support function for mirror status requests.
- */
- int (*status)(struct dirty_log *log, status_type_t status_type,
- char *result, unsigned int maxlen);
-
- /*
- * Return the code describing what to do in the event
- * of a device failure.
- */
- int (*get_failure_response)(struct dirty_log *log);
-
- /*
- * Returns: 0, 1
- *
- * This is necessary for cluster mirroring. It provides
- * a way to detect recovery on another node, so we
- * aren't writing concurrently. This function is likely
- * to block (when a cluster log is used).
- */
- int (*is_remote_recovering)(struct dirty_log *log, region_t region);
-
- int (*reserved[5])(int a);
-};
-
-int dm_register_dirty_log_type(struct dirty_log_type *type);
-int dm_unregister_dirty_log_type(struct dirty_log_type *type);
-
-
-/*
- * Make sure you use these two functions, rather than calling
- * type->constructor/destructor() directly.
- */
-struct dirty_log *dm_create_dirty_log(const char *type_name, struct dm_target *ti,
- unsigned int argc, char **argv);
-void dm_destroy_dirty_log(struct dirty_log *log);
-
-/*
- * init/exit functions.
- */
-int dm_dirty_log_init(void);
-void dm_dirty_log_exit(void);
-
-#endif
diff --git a/cmirror-kernel/src/dm.h-copy b/cmirror-kernel/src/dm.h-copy
deleted file mode 100644
index 52eb2b9..0000000
--- a/cmirror-kernel/src/dm.h-copy
+++ /dev/null
@@ -1,149 +0,0 @@
-/*
- * Internal header file for device mapper
- *
- * Copyright (C) 2001, 2002 Sistina Software
- * Copyright (C) 2004-2006 Red Hat, Inc. All rights reserved.
- *
- * This file is released under the LGPL.
- */
-
-#ifndef DM_INTERNAL_H
-#define DM_INTERNAL_H
-
-#include <linux/fs.h>
-#include <linux/device-mapper.h>
-#include <linux/list.h>
-#include <linux/blkdev.h>
-#include <linux/hdreg.h>
-
-#define DM_NAME "device-mapper"
-
-#define DMERR(f, arg...) printk(KERN_ERR DM_NAME ": " DM_MSG_PREFIX ": " f "\n", ## arg)
-#define DMWARN(f, arg...) printk(KERN_WARNING DM_NAME ": " DM_MSG_PREFIX ": " f "\n", ## arg)
-#define DMINFO(f, arg...) printk(KERN_INFO DM_NAME ": " DM_MSG_PREFIX ": " f "\n", ## arg)
-
-#define DMEMIT(x...) sz += ((sz >= maxlen) ? \
- 0 : scnprintf(result + sz, maxlen - sz, x))
-
-#define SECTOR_SHIFT 9
-
-/*
- * Definitions of return values from target end_io function.
- */
-#define DM_ENDIO_INCOMPLETE 1
-#define DM_ENDIO_REQUEUE 2
-
-/*
- * Definitions of return values from target map function.
- */
-#define DM_MAPIO_SUBMITTED 0
-#define DM_MAPIO_REMAPPED 1
-#define DM_MAPIO_REQUEUE DM_ENDIO_REQUEUE
-
-/*
- * Suspend feature flags
- */
-#define DM_SUSPEND_LOCKFS_FLAG (1 << 0)
-#define DM_SUSPEND_NOFLUSH_FLAG (1 << 1)
-
-/*
- * List of devices that a metadevice uses and should open/close.
- */
-struct dm_dev {
- struct list_head list;
-
- atomic_t count;
- int mode;
- struct block_device *bdev;
- char name[16];
-};
-
-struct dm_table;
-
-/*-----------------------------------------------------------------
- * Internal table functions.
- *---------------------------------------------------------------*/
-void dm_table_event_callback(struct dm_table *t,
- void (*fn)(void *), void *context);
-struct dm_target *dm_table_get_target(struct dm_table *t, unsigned int index);
-struct dm_target *dm_table_find_target(struct dm_table *t, sector_t sector);
-void dm_table_set_restrictions(struct dm_table *t, struct request_queue *q);
-struct list_head *dm_table_get_devices(struct dm_table *t);
-void dm_table_presuspend_targets(struct dm_table *t);
-void dm_table_postsuspend_targets(struct dm_table *t);
-int dm_table_resume_targets(struct dm_table *t);
-int dm_table_any_congested(struct dm_table *t, int bdi_bits);
-void dm_table_unplug_all(struct dm_table *t);
-int dm_table_flush_all(struct dm_table *t);
-
-/*-----------------------------------------------------------------
- * A registry of target types.
- *---------------------------------------------------------------*/
-int dm_target_init(void);
-void dm_target_exit(void);
-struct target_type *dm_get_target_type(const char *name);
-void dm_put_target_type(struct target_type *t);
-int dm_target_iterate(void (*iter_func)(struct target_type *tt,
- void *param), void *param);
-
-/*-----------------------------------------------------------------
- * Useful inlines.
- *---------------------------------------------------------------*/
-static inline int array_too_big(unsigned long fixed, unsigned long obj,
- unsigned long num)
-{
- return (num > (ULONG_MAX - fixed) / obj);
-}
-
-/*
- * Ceiling(n / sz)
- */
-#define dm_div_up(n, sz) (((n) + (sz) - 1) / (sz))
-
-#define dm_sector_div_up(n, sz) ( \
-{ \
- sector_t _r = ((n) + (sz) - 1); \
- sector_div(_r, (sz)); \
- _r; \
-} \
-)
-
-/*
- * ceiling(n / size) * size
- */
-#define dm_round_up(n, sz) (dm_div_up((n), (sz)) * (sz))
-
-static inline sector_t to_sector(unsigned long n)
-{
- return (n >> 9);
-}
-
-static inline unsigned long to_bytes(sector_t n)
-{
- return (n << 9);
-}
-
-int dm_split_args(int *argc, char ***argvp, char *input);
-
-/*
- * The device-mapper can be driven through one of two interfaces;
- * ioctl or filesystem, depending which patch you have applied.
- */
-int dm_interface_init(void);
-void dm_interface_exit(void);
-
-/*
- * Targets for linear and striped mappings
- */
-int dm_linear_init(void);
-void dm_linear_exit(void);
-
-int dm_stripe_init(void);
-void dm_stripe_exit(void);
-
-void *dm_vcalloc(unsigned long nmemb, unsigned long elem_size);
-union map_info *dm_get_mapinfo(struct bio *bio);
-int dm_open_count(struct mapped_device *md);
-int dm_lock_for_deletion(struct mapped_device *md);
-
-#endif
diff --git a/cmirror/src/Makefile b/cmirror/src/Makefile
index c4e3b8b..67ee0d5 100644
--- a/cmirror/src/Makefile
+++ b/cmirror/src/Makefile
@@ -23,7 +23,7 @@ TMP_INCLUDE = $(shell if [ -e ${KERNEL_SRC}/include/linux/dm-clog-tfr.h ]; then
echo '-I${incdir}'; else \
echo ''; fi)
-SOURCES = $(shell ls *.c)
+SOURCES = clogd.c cluster.c functions.c link_mon.c local.c logging.c
ifneq (${TMP_INCLUDE}, )
INCLUDE += ${TMP_INCLUDE} -I.
diff --git a/cmirror/src/clogd.c b/cmirror/src/clogd.c
index 99543ba..9dd1413 100644
--- a/cmirror/src/clogd.c
+++ b/cmirror/src/clogd.c
@@ -19,7 +19,6 @@
#include "functions.h"
#include "local.h"
#include "cluster.h"
-#include "queues.h"
#include "common.h"
#include "logging.h"
#include "link_mon.h"
@@ -118,17 +117,16 @@ static void sig_handler(int sig)
}
static void process_signal(int sig){
- int r;
+ int r = 0;
+
switch(sig) {
case SIGINT:
case SIGQUIT:
case SIGTERM:
case SIGHUP:
- r = queue_status(0);
r += log_status(0);
break;
case SIGUSR1:
- queue_status(1);
log_status(1);
return;
case SIGUSR2:
@@ -208,9 +206,6 @@ static void daemonize(void)
LOG_ERROR("Unable to initialize checkpoint service");
LOG_ERROR("Has the cluster infrastructure been started?");
break;
- case EXIT_QUEUE_NOMEM:
- LOG_ERROR("Unable to allocate memory for queues");
- break;
case EXIT_FAILURE:
LOG_ERROR("Failed to start: Generic error");
break;
@@ -256,8 +251,7 @@ static void init_all(void)
int r;
if ((r = init_local()) ||
- (r = init_cluster()) ||
- (r = init_queues())) {
+ (r = init_cluster())) {
exit(r);
}
}
@@ -271,7 +265,6 @@ static void cleanup_all(void)
{
cleanup_local();
cleanup_cluster();
- cleanup_queues();
}
static void set_priority(void)
diff --git a/cmirror/src/cluster.c b/cmirror/src/cluster.c
index 59aa1d6..af30aa2 100644
--- a/cmirror/src/cluster.c
+++ b/cmirror/src/cluster.c
@@ -2,6 +2,8 @@
#include <string.h>
#include <sys/types.h>
#include <unistd.h>
+#include <stdint.h>
+#include <stdlib.h>
#include <sys/socket.h> /* These are for OpenAIS CPGs */
#include <sys/select.h>
@@ -12,7 +14,8 @@
#include <openais/cpg.h>
#include <openais/saCkpt.h>
-#include "queues.h"
+#include "linux/dm-clog-tfr.h"
+#include "list.h"
#include "functions.h"
#include "local.h"
#include "common.h"
@@ -53,15 +56,12 @@
#define DM_CLOG_RESPONSE 0x1000 /* in last byte of 32-bit value */
#define DM_CLOG_CHECKPOINT_READY 21
#define DM_CLOG_MEMBER_JOIN 22
-#define DM_CLOG_MEMBER_LEAVE 23
#define _RQ_TYPE(x) \
((x) == DM_CLOG_CHECKPOINT_READY) ? "DM_CLOG_CHECKPOINT_READY": \
((x) == DM_CLOG_MEMBER_JOIN) ? "DM_CLOG_MEMBER_JOIN": \
- ((x) == DM_CLOG_MEMBER_LEAVE) ? "DM_CLOG_MEMBER_LEAVE": \
RQ_TYPE((x) & ~DM_CLOG_RESPONSE)
-
static uint32_t my_cluster_id = 0xDEAD;
static SaCkptHandleT ckpt_handle = 0;
static SaCkptCallbacksT callbacks = { 0, 0 };
@@ -98,11 +98,10 @@ struct clog_cpg {
int state;
int cpg_state; /* FIXME: debugging */
int free_me;
- int resend_requests;
int delay;
- struct queue *delay_queue;
- struct queue *startup_queue;
- struct queue *cluster_queue;
+ int resend_requests;
+ struct list_head startup_list;
+ struct list_head working_list;
int checkpoints_needed;
uint32_t checkpoint_requesters[10];
@@ -148,16 +147,6 @@ int cluster_send(struct clog_tfr *tfr)
return -EINVAL;
}
- if ((tfr->request_type != DM_CLOG_CHECKPOINT_READY) &&
- (tfr->request_type != DM_CLOG_MEMBER_LEAVE) &&
- (entry->delay || !queue_empty(entry->delay_queue))) {
- LOG_COND(log_resend_requests, "[%s] Delaying request%s, %s/%u",
- SHORT_UUID(tfr->uuid), queue_empty(entry->delay_queue) ? "" : "*",
- _RQ_TYPE(tfr->request_type), tfr->seq);
- queue_add_tail(tfr, entry->delay_queue);
- return 1;
- }
-
do {
r = cpg_mcast_joined(entry->handle, CPG_TYPE_AGREED, &iov, 1);
if ((r != SA_AIS_ERR_TRY_AGAIN) || (count++ > 5))
@@ -175,14 +164,19 @@ int cluster_send(struct clog_tfr *tfr)
return -EBADE;
}
-static int clog_tfr_cmp(struct clog_tfr *a, struct clog_tfr *b)
+static struct clog_tfr *get_matching_tfr(struct clog_tfr *t, struct list_head *l)
{
- int r = 0;
+ struct clog_tfr *match;
+ struct list_head *p, *n;
- if (a->seq == b->seq)
- r = 1;
-
- return r;
+ list_for_each_safe(p, n, l) {
+ match = (struct clog_tfr *)p;
+ if (match->seq == t->seq) {
+ list_del_init(p);
+ return match;
+ }
+ }
+ return NULL;
}
static int handle_cluster_request(struct clog_cpg *entry,
@@ -201,7 +195,9 @@ static int handle_cluster_request(struct clog_cpg *entry,
(tfr->originator == my_cluster_id))
r = do_request(tfr, server);
- if (server && (tfr->request_type != DM_CLOG_CLEAR_REGION)) {
+ if (server &&
+ (tfr->request_type != DM_CLOG_CLEAR_REGION) &&
+ (tfr->request_type != DM_CLOG_POSTSUSPEND)) {
tfr->request_type |= DM_CLOG_RESPONSE;
/*
@@ -227,10 +223,10 @@ static int handle_cluster_response(struct clog_cpg *entry, struct clog_tfr *tfr)
return 0;
tfr->request_type &= ~DM_CLOG_RESPONSE;
- orig_tfr = queue_remove_match(entry->cluster_queue, clog_tfr_cmp, tfr);
+ orig_tfr = get_matching_tfr(tfr, &entry->working_list);
if (!orig_tfr) {
- struct list_head l, *p, *n;
+ struct list_head *p, *n;
struct clog_tfr *t;
/* Unable to find match for response */
@@ -239,34 +235,14 @@ static int handle_cluster_response(struct clog_cpg *entry, struct clog_tfr *tfr)
SHORT_UUID(tfr->uuid),
_RQ_TYPE(tfr->request_type), tfr->seq);
- INIT_LIST_HEAD(&l);
- queue_remove_all(&l, cluster_queue);
- LOG_ERROR("Current global list:");
- if (list_empty(&l))
- LOG_ERROR(" [none]");
-
- list_for_each_safe(p, n, &l) {
- list_del_init(p);
- t = (struct clog_tfr *)p;
- LOG_ERROR(" [%s] %s:%u", SHORT_UUID(t->uuid),
- _RQ_TYPE(t->request_type),
- t->seq);
- queue_add_tail(t, cluster_queue);
- }
-
- INIT_LIST_HEAD(&l);
- queue_remove_all(&l, entry->cluster_queue);
LOG_ERROR("Current local list:");
- if (list_empty(&l))
+ if (list_empty(&entry->working_list))
LOG_ERROR(" [none]");
- list_for_each_safe(p, n, &l) {
- list_del_init(p);
+ list_for_each_safe(p, n, &entry->working_list) {
t = (struct clog_tfr *)p;
LOG_ERROR(" [%s] %s:%u", SHORT_UUID(t->uuid),
- _RQ_TYPE(t->request_type),
- t->seq);
- queue_add(t, entry->cluster_queue);
+ _RQ_TYPE(t->request_type), t->seq);
}
return -EINVAL;
@@ -282,11 +258,12 @@ static int handle_cluster_response(struct clog_cpg *entry, struct clog_tfr *tfr)
/* FIXME: Ensure memcpy cannot explode */
memcpy(orig_tfr, tfr, sizeof(*tfr) + tfr->data_size);
- INIT_LIST_HEAD((struct list_head *)&orig_tfr->private);
+
r = kernel_send(orig_tfr);
if (r)
LOG_ERROR("Failed to send response to kernel");
+ free(orig_tfr);
return r;
}
@@ -395,7 +372,7 @@ static int export_checkpoint(struct checkpoint_data *cp)
SaNameT name;
SaAisErrorT rv;
struct clog_tfr *tfr;
- int len;
+ int len, r = 0;
char buf[32];
LOG_DBG("Sending checkpointed data to %u", cp->requester);
@@ -531,33 +508,24 @@ rr_create_retry:
LOG_DBG("export_checkpoint: closing checkpoint");
saCkptCheckpointClose(h);
- tfr = queue_remove(free_queue);
+ tfr = malloc(DM_CLOG_TFR_SIZE);
if (!tfr) {
- LOG_PRINT("export_checkpoint: Preallocated transfer structs exhausted");
- tfr = malloc(DM_CLOG_TFR_SIZE);
- if (!tfr) {
- LOG_ERROR("export_checkpoint: Unable to allocate transfer structs");
- return -ENOMEM;
- }
+ LOG_ERROR("export_checkpoint: Unable to allocate transfer structs");
+ return -ENOMEM;
}
memset(tfr, 0, sizeof(*tfr));
+
INIT_LIST_HEAD((struct list_head *)&tfr->private);
tfr->request_type = DM_CLOG_CHECKPOINT_READY;
tfr->originator = cp->requester; /* FIXME: hack to overload meaning of originator */
strncpy(tfr->uuid, cp->uuid, CPG_MAX_NAME_LENGTH);
/* FIXME: Clean-up and use better variable for rtn */
- len = cluster_send(tfr);
- if (len < 0) {
+ r = cluster_send(tfr);
+ if (r)
LOG_ERROR("Failed to send checkpoint ready notice");
- queue_add(tfr, free_queue);
- return len;
- } else if (!len)
- queue_add(tfr, free_queue);
-
- LOG_DBG("[%s] Checkpoint ready, notification sent to %u",
- SHORT_UUID(cp->uuid), cp->requester);
+ free(tfr);
return 0;
}
@@ -749,87 +717,63 @@ static void do_checkpoints(struct clog_cpg *entry)
static int resend_requests(struct clog_cpg *entry)
{
int r = 0;
- struct list_head resend, delay, *p, *n;
+ struct list_head *p, *n;
struct clog_tfr *tfr;
- if (entry->delay)
+ if (!entry->resend_requests)
return 0;
- INIT_LIST_HEAD(&resend);
- INIT_LIST_HEAD(&delay);
-
- queue_remove_all(&delay, entry->delay_queue);
-
- if (entry->resend_requests) {
- entry->resend_requests = 0;
-
- log_resp_rec = 0;
- queue_remove_all(&resend, entry->cluster_queue);
+ if (entry->state != VALID)
+ return 0;
- list_for_each_safe(p, n, &resend) {
- list_del_init(p);
- tfr = (struct clog_tfr *)p;
+ entry->resend_requests = 0;
- if (!strcmp(entry->name.value, tfr->uuid)) {
- switch (tfr->request_type) {
- case DM_CLOG_POSTSUSPEND:
- /*
- * Don't resend DM_CLOG_POSTSUSPEND request, it will
- * be handled when we get our own config leave
- */
- queue_add_tail(tfr, cluster_queue);
- break;
- case DM_CLOG_RESUME:
- /* We are only concerned about this request locally */
- case DM_CLOG_SET_REGION_SYNC:
- /*
- * Some requests simply do not need to be resent.
- * If it is a request that just changes log state,
- * then it doesn't need to be resent (everyone makes
- * updates).
- */
- LOG_COND(log_resend_requests,
- "[%s] Skipping resend of %s/#%u...",
- SHORT_UUID(entry->name.value),
- _RQ_TYPE(tfr->request_type), tfr->seq);
- tfr->data_size = 0;
- kernel_send(tfr);
-
- break;
- default:
- /*
- * If an action or a response is required, then
- * the request must be resent.
- */
- r = 1;
- log_resp_rec++;
- LOG_COND(log_resend_requests,
- "[%s] Resending %s(#%u) due to new server(%u)",
- SHORT_UUID(entry->name.value),
- _RQ_TYPE(tfr->request_type),
- tfr->seq, entry->lowest_id);
- queue_add_tail(tfr, cluster_queue);
- if (cluster_send(tfr) < 0)
- LOG_ERROR("Failed resend");
- }
- }
- }
- }
-
- list_for_each_safe(p, n, &delay) {
+ list_for_each_safe(p, n, &entry->working_list) {
list_del_init(p);
tfr = (struct clog_tfr *)p;
- LOG_COND(log_resend_requests,
- "[%s] Sending delayed request, %s/#%u",
- SHORT_UUID(entry->name.value),
- _RQ_TYPE(tfr->request_type),
- tfr->seq);
- queue_add_tail(tfr, cluster_queue);
+ if (strcmp(entry->name.value, tfr->uuid)) {
+ LOG_ERROR("[%s] Stray request from another log (%s)",
+ SHORT_UUID(entry->name.value),
+ SHORT_UUID(tfr->uuid));
+ free(tfr);
+ continue;
+ }
- if ((tfr->request_type != DM_CLOG_POSTSUSPEND) &&
- (cluster_send(tfr) < 0))
- LOG_ERROR("Failed resend");
+ switch (tfr->request_type) {
+ case DM_CLOG_RESUME:
+ /* We are only concerned about this request locally */
+ case DM_CLOG_SET_REGION_SYNC:
+ /*
+ * Some requests simply do not need to be resent.
+ * If it is a request that just changes log state,
+ * then it doesn't need to be resent (everyone makes
+ * updates).
+ */
+ LOG_COND(log_resend_requests,
+ "[%s] Skipping resend of %s/#%u...",
+ SHORT_UUID(entry->name.value),
+ _RQ_TYPE(tfr->request_type), tfr->seq);
+ tfr->data_size = 0;
+ kernel_send(tfr);
+
+ break;
+
+ default:
+ /*
+ * If an action or a response is required, then
+ * the request must be resent.
+ */
+ LOG_COND(log_resend_requests,
+ "[%s] Resending %s(#%u) due to new server(%u)",
+ SHORT_UUID(entry->name.value),
+ _RQ_TYPE(tfr->request_type),
+ tfr->seq, entry->lowest_id);
+ r = cluster_send(tfr);
+ if (r < 0)
+ LOG_ERROR("Failed resend");
+ }
+ free(tfr);
}
return r;
@@ -837,28 +781,21 @@ static int resend_requests(struct clog_cpg *entry)
static int do_cluster_work(void *data)
{
- int i, go_again = 1;
int r = SA_AIS_OK;
struct clog_cpg *entry, *tmp;
- for (i = 0; ((i < 5) && go_again); i++) {
- go_again = 0;
- list_for_each_entry_safe(entry, tmp, &clog_cpg_list, list) {
- r = cpg_dispatch(entry->handle, CPG_DISPATCH_ALL);
- if (r != SA_AIS_OK)
- LOG_ERROR("cpg_dispatch failed: %s", str_ais_error(r));
-
- if (entry->free_me) {
- free(entry->cluster_queue);
- free(entry->delay_queue);
- free(entry->startup_queue);
- free(entry);
- continue;
- }
- do_checkpoints(entry);
+ list_for_each_entry_safe(entry, tmp, &clog_cpg_list, list) {
+ r = cpg_dispatch(entry->handle, CPG_DISPATCH_ALL);
+ if (r != SA_AIS_OK)
+ LOG_ERROR("cpg_dispatch failed: %s", str_ais_error(r));
- go_again = resend_requests(entry);
+ if (entry->free_me) {
+ free(entry);
+ continue;
}
+ do_checkpoints(entry);
+
+ resend_requests(entry);
}
return (r == SA_AIS_OK) ? 0 : -1; /* FIXME: good error number? */
@@ -873,92 +810,71 @@ static void cpg_message_callback(cpg_handle_t handle, struct cpg_name *gname,
int i_am_server;
int i_was_server;
int response = 0;
+ struct list_head *p, *n;
struct clog_tfr *tfr = msg;
- struct clog_tfr *startup_tfr = NULL;
+ struct clog_tfr *tmp_tfr = NULL;
struct clog_cpg *match;
- if (msg_len != (sizeof(*tfr) + tfr->data_size))
- LOG_ERROR("Badly sized message received from cluster.");
-
- if (tfr->request_type & DM_CLOG_RESPONSE)
- LOG_DBG("Response to %u from %u received [%s/%u]",
- tfr->originator, nodeid,
- _RQ_TYPE(tfr->request_type & ~DM_CLOG_RESPONSE),
- tfr->seq);
- else
- LOG_DBG("Request from %u received [%s/%u]",
- nodeid, _RQ_TYPE(tfr->request_type),
- tfr->seq);
-
- if (my_cluster_id == 0xDEAD) {
- LOG_ERROR("[%s] Message from %u before init [%s/%u]",
- SHORT_UUID(tfr->uuid), nodeid,
- _RQ_TYPE(tfr->request_type), tfr->seq);
- return;
- }
-
match = find_clog_cpg(handle);
if (!match) {
LOG_ERROR("Unable to find clog_cpg for cluster message");
return;
}
- if (match->lowest_id == 0xDEAD) {
- LOG_ERROR("[%s] Message from %u before init* [%s/%u]",
- SHORT_UUID(tfr->uuid), nodeid,
- _RQ_TYPE(tfr->request_type), tfr->seq);
- return;
- }
-
- if (nodeid == my_cluster_id) {
- struct clog_tfr *orig_tfr;
-
- orig_tfr = queue_remove_match(cluster_queue, clog_tfr_cmp, tfr);
- if (orig_tfr)
- queue_add_tail(orig_tfr, match->cluster_queue);
+ if ((nodeid == my_cluster_id) &&
+ !(tfr->request_type & DM_CLOG_RESPONSE) &&
+ (tfr->request_type != DM_CLOG_CLEAR_REGION)) {
+ tmp_tfr = malloc(DM_CLOG_TFR_SIZE);
+ if (!tmp_tfr) {
+ /*
+ * FIXME: It may be possible to continue... but we
+ * would not be able to resend any messages that might
+ * be necessary during membership changes
+ */
+ LOG_ERROR("[%s] Unable to record request: -ENOMEM",
+ SHORT_UUID(tfr->uuid));
+ return;
+ }
+ memcpy(tmp_tfr, tfr, sizeof(*tfr) + tfr->data_size);
+ list_add_tail((struct list_head *)&tmp_tfr->private, &match->working_list);
}
- if (tfr->request_type == DM_CLOG_MEMBER_LEAVE) {
+ if (tfr->request_type == DM_CLOG_POSTSUSPEND) {
/*
* If the server (lowest_id) indicates it is leaving,
* then we must resend any outstanding requests. However,
* we do not want to resend them if the next server in
* line is in the process of leaving.
*/
- if (nodeid == my_cluster_id)
- LOG_COND(log_resend_requests, "[%s] I am leaving (2).....",
+ if (nodeid == my_cluster_id) {
+ LOG_COND(log_resend_requests, "[%s] I am leaving.1.....",
SHORT_UUID(tfr->uuid));
-
- if ((nodeid == match->lowest_id) &&
- (nodeid != my_cluster_id)) {
- struct list_head l, *p, *n;
- struct clog_tfr *t;
-
- log_resp_rec++;
-
- match->resend_requests = 1;
- LOG_COND(log_resend_requests, "[%s] %u is leaving, resend required%s",
- SHORT_UUID(tfr->uuid), nodeid,
- (queue_empty(match->cluster_queue)) ? " -- cluster_queue empty": "");
+ } else {
+ if (nodeid < my_cluster_id) {
+ if (nodeid == match->lowest_id) {
+ struct list_head *p, *n;
+
+ match->resend_requests = 1;
+ LOG_COND(log_resend_requests, "[%s] %u is leaving, resend required%s",
+ SHORT_UUID(tfr->uuid), nodeid,
+ (list_empty(&match->working_list)) ? " -- working_list empty": "");
- INIT_LIST_HEAD(&l);
- queue_remove_all(&l, match->cluster_queue);
- list_for_each_safe(p, n, &l) {
- list_del_init(p);
- t = (struct clog_tfr *)p;
-
- LOG_COND(log_resend_requests,
- "[%s] %s/%u",
- SHORT_UUID(t->uuid), _RQ_TYPE(t->request_type), t->seq);
- queue_add_tail(t, match->cluster_queue);
+ list_for_each_safe(p, n, &match->working_list) {
+ tmp_tfr = (struct clog_tfr *)p;
+
+ LOG_COND(log_resend_requests,
+ "[%s] %s/%u",
+ SHORT_UUID(tmp_tfr->uuid),
+ _RQ_TYPE(tmp_tfr->request_type), tmp_tfr->seq);
+ }
+ }
+
+ match->delay++;
+ LOG_COND(log_resend_requests, "[%s] %u is leaving, delay = %d",
+ SHORT_UUID(tfr->uuid), nodeid, match->delay);
}
+ goto out;
}
- if (nodeid < my_cluster_id) {
- match->delay++;
- LOG_COND(log_resend_requests, "[%s] %u is leaving, delay = %d",
- SHORT_UUID(tfr->uuid), nodeid, match->delay);
- }
- goto out;
}
/*
@@ -984,26 +900,29 @@ static void cpg_message_callback(cpg_handle_t handle, struct cpg_name *gname,
SHORT_UUID(match->name.value), nodeid);
match->state = VALID;
- while ((startup_tfr = queue_remove(match->startup_queue))) {
- if (startup_tfr->request_type == DM_CLOG_MEMBER_JOIN) {
+ list_for_each_safe(p, n, &match->startup_list) {
+ list_del_init(p);
+ tmp_tfr = (struct clog_tfr *)p;
+ if (tmp_tfr->request_type == DM_CLOG_MEMBER_JOIN) {
struct checkpoint_data *new;
- new = prepare_checkpoint(match, startup_tfr->originator);
+ new = prepare_checkpoint(match, tmp_tfr->originator);
if (!new) {
/* FIXME: Need better error handling */
LOG_ERROR("Failed to prepare checkpoint for %u!!!",
- startup_tfr->originator);
+ tmp_tfr->originator);
+ free(tmp_tfr);
goto out;
}
LOG_COND(log_checkpoint, "[%s] Checkpoint prepared for %u",
- SHORT_UUID(tfr->uuid), startup_tfr->originator);
+ SHORT_UUID(tfr->uuid), tmp_tfr->originator);
} else {
- LOG_DBG("Processing delayed request %d: %s",
- match->startup_queue->count,
- _RQ_TYPE(startup_tfr->request_type));
- i_was_server = (startup_tfr->error == my_cluster_id) ? 1 : 0;
- startup_tfr->error = 0;
- r = handle_cluster_request(match, startup_tfr, i_was_server);
+ LOG_DBG("[%s] Processing delayed request: %s",
+ SHORT_UUID(tmp_tfr->uuid),
+ _RQ_TYPE(tmp_tfr->request_type));
+ i_was_server = (tmp_tfr->error == my_cluster_id) ? 1 : 0;
+ tmp_tfr->error = 0;
+ r = handle_cluster_request(match, tmp_tfr, i_was_server);
if (r) {
LOG_ERROR("Error while processing delayed CPG message");
@@ -1011,10 +930,11 @@ static void cpg_message_callback(cpg_handle_t handle, struct cpg_name *gname,
* FIXME: If we error out here, we will never get
* another opportunity to retry these requests
*/
+ free(tmp_tfr);
goto out;
}
}
- queue_add(startup_tfr, free_queue);
+ free(tmp_tfr);
}
}
}
@@ -1058,23 +978,18 @@ static void cpg_message_callback(cpg_handle_t handle, struct cpg_name *gname,
if (match->state == INVALID) {
LOG_DBG("Log not valid yet, storing request");
- startup_tfr = queue_remove(free_queue);
- if (!startup_tfr) {
- LOG_PRINT("cpg_message_callback: Preallocated"
- " transfer structs exhausted");
- startup_tfr = malloc(DM_CLOG_TFR_SIZE);
- if (!startup_tfr) {
- LOG_ERROR("cpg_message_callback: Unable to"
- " allocate transfer structs");
- r = -ENOMEM; /* FIXME: Better error #? */
- goto out;
- }
+ tmp_tfr = malloc(DM_CLOG_TFR_SIZE);
+ if (!tmp_tfr) {
+ LOG_ERROR("cpg_message_callback: Unable to"
+ " allocate transfer structs");
+ r = -ENOMEM; /* FIXME: Better error #? */
+ goto out;
}
- memcpy(startup_tfr, tfr, sizeof(*tfr) + tfr->data_size);
- INIT_LIST_HEAD((struct list_head *)&startup_tfr->private);
- startup_tfr->error = match->lowest_id;
- queue_add_tail(startup_tfr, match->startup_queue);
+ memcpy(tmp_tfr, tfr, sizeof(*tfr) + tfr->data_size);
+ tmp_tfr->error = match->lowest_id;
+ list_add_tail((struct list_head *)&tmp_tfr->private,
+ &match->startup_list);
goto out;
}
@@ -1129,13 +1044,6 @@ static void cpg_join_callback(struct clog_cpg *match,
uint32_t lowest = match->lowest_id;
struct clog_tfr *tfr;
- {
- idx++;
- idx = idx % DEBUGGING_HISTORY;
- sprintf(debugging[idx], "+++ UUID=%s %u join +++",
- SHORT_UUID(match->name.value), joined->nodeid);
- }
-
/* Assign my_cluster_id */
if ((my_cluster_id == 0xDEAD) && (joined->pid == my_pid))
my_cluster_id = joined->nodeid;
@@ -1155,29 +1063,24 @@ static void cpg_join_callback(struct clog_cpg *match,
/*
* FIXME: remove checkpoint_requesters/checkpoints_needed, and use
- * the startup_queue interface exclusively
+ * the startup_list interface exclusively
*/
- if (queue_empty(match->startup_queue) && (match->state == VALID)) {
+ if (list_empty(&match->startup_list) && (match->state == VALID)) {
match->checkpoint_requesters[match->checkpoints_needed++] = joined->nodeid;
goto out;
}
- tfr = queue_remove(free_queue);
+ tfr = malloc(DM_CLOG_TFR_SIZE);
if (!tfr) {
- LOG_PRINT("cpg_config_callback: "
- "Preallocated transfer structs exhausted");
- tfr = malloc(DM_CLOG_TFR_SIZE);
- if (!tfr) {
- LOG_ERROR("cpg_config_callback: "
- "Unable to allocate transfer structs");
- LOG_ERROR("cpg_config_callback: "
- "Unable to perform checkpoint");
- goto out;
- }
+ LOG_ERROR("cpg_config_callback: "
+ "Unable to allocate transfer structs");
+ LOG_ERROR("cpg_config_callback: "
+ "Unable to perform checkpoint");
+ goto out;
}
tfr->request_type = DM_CLOG_MEMBER_JOIN;
tfr->originator = joined->nodeid;
- queue_add_tail(tfr, match->startup_queue);
+ list_add_tail((struct list_head *)&tfr->private, &match->startup_list);
out:
/* Find the lowest_id, i.e. the server */
@@ -1199,6 +1102,10 @@ out:
LOG_COND(log_membership_change, "[%s] Server unchanged at %u (%u joined)",
SHORT_UUID(match->name.value),
lowest, joined->nodeid);
+ idx++;
+ idx = idx % DEBUGGING_HISTORY;
+ sprintf(debugging[idx], "+++ UUID=%s %u join +++",
+ SHORT_UUID(match->name.value), joined->nodeid);
}
static void cpg_leave_callback(struct clog_cpg *match,
@@ -1207,7 +1114,7 @@ static void cpg_leave_callback(struct clog_cpg *match,
int member_list_entries)
{
int i, fd;
- struct list_head l, *p, *n;
+ struct list_head *p, *n;
uint32_t lowest = match->lowest_id;
struct clog_tfr *tfr;
@@ -1228,48 +1135,17 @@ static void cpg_leave_callback(struct clog_cpg *match,
cluster_postsuspend(match->name.value);
- INIT_LIST_HEAD(&l);
- queue_remove_all(&l, cluster_queue);
- list_for_each_safe(p, n, &l) {
+ list_for_each_safe(p, n, &match->working_list) {
list_del_init(p);
tfr = (struct clog_tfr *)p;
- /* Leave in the cluster_queue if not of this log */
- if (strcmp(match->name.value, tfr->uuid)) {
- queue_add_tail(tfr, cluster_queue);
- continue;
- }
-
if (tfr->request_type == DM_CLOG_POSTSUSPEND)
kernel_send(tfr);
- else
- queue_add(tfr, free_queue);
- }
-
- INIT_LIST_HEAD(&l);
- queue_remove_all(&l, match->cluster_queue);
- list_for_each_safe(p, n, &l) {
- list_del_init(p);
- tfr = (struct clog_tfr *)p;
-
- if (tfr->request_type == DM_CLOG_POSTSUSPEND)
- kernel_send(tfr);
- else
- queue_add(tfr, free_queue);
+ free(tfr);
}
cpg_finalize(match->handle);
- /* FIXME: redundant */
- if (match->startup_queue->count) {
- LOG_ERROR("%d startup items remain in cluster log",
- match->startup_queue->count);
- while (!queue_empty(match->startup_queue)) {
- tfr = queue_remove(match->startup_queue);
- queue_add(tfr, free_queue);
- }
- }
-
match->free_me = 1;
match->lowest_id = 0xDEAD;
match->state = INVALID;
@@ -1277,11 +1153,11 @@ static void cpg_leave_callback(struct clog_cpg *match,
if (left->nodeid < my_cluster_id) {
match->delay = (match->delay > 0) ? match->delay - 1 : 0;
- if (!match->delay && queue_empty(match->cluster_queue))
+ if (!match->delay && list_empty(&match->working_list))
match->resend_requests = 0;
LOG_COND(log_resend_requests, "[%s] %u has left, delay = %d%s",
SHORT_UUID(match->name.value), left->nodeid,
- match->delay, (queue_empty(match->cluster_queue)) ? " -- cluster_queue empty": "");
+ match->delay, (list_empty(&match->working_list)) ? " -- working_list empty": "");
}
/* Find the lowest_id, i.e. the server */
@@ -1369,33 +1245,8 @@ int create_cluster_cpg(char *str)
memset(new, 0, sizeof(*new));
INIT_LIST_HEAD(&new->list);
new->lowest_id = 0xDEAD;
-
- new->startup_queue = malloc(sizeof(struct queue));
- if (!new->startup_queue) {
- LOG_ERROR("Unable to allocate memory for clog_cpg");
- r = -ENOMEM;
- goto fail;
- }
- INIT_LIST_HEAD(&(new->startup_queue->list));
- new->startup_queue->count = 0;
-
- new->delay_queue = malloc(sizeof(struct queue));
- if (!new->delay_queue) {
- LOG_ERROR("Unable to allocate memory for clog_cpg");
- r = -ENOMEM;
- goto fail;
- }
- INIT_LIST_HEAD(&(new->delay_queue->list));
- new->delay_queue->count = 0;
-
- new->cluster_queue = malloc(sizeof(struct queue));
- if (!new->cluster_queue) {
- LOG_ERROR("Unable to allocate memory for clog_cpg");
- r = -ENOMEM;
- goto fail;
- }
- INIT_LIST_HEAD(&(new->cluster_queue->list));
- new->cluster_queue->count = 0;
+ INIT_LIST_HEAD(&new->startup_list);
+ INIT_LIST_HEAD(&new->working_list);
size = ((strlen(str) + 1) > CPG_MAX_NAME_LENGTH) ?
CPG_MAX_NAME_LENGTH : (strlen(str) + 1);
@@ -1405,15 +1256,15 @@ int create_cluster_cpg(char *str)
r = cpg_initialize(&new->handle, &cpg_callbacks);
if (r != SA_AIS_OK) {
LOG_ERROR("cpg_initialize failed: Cannot join cluster");
- r = -EPERM;
- goto fail;
+ free(new);
+ return -EPERM;
}
r = cpg_join(new->handle, &new->name);
if (r != SA_AIS_OK) {
LOG_ERROR("cpg_join failed: Cannot join cluster");
- r = -EPERM;
- goto fail;
+ free(new);
+ return -EPERM;
}
new->cpg_state = VALID;
@@ -1426,18 +1277,6 @@ int create_cluster_cpg(char *str)
links_register(r, "cluster", do_cluster_work, NULL);
return 0;
-
-fail:
- if (new) {
- if (new->startup_queue)
- free(new->startup_queue);
- if (new->delay_queue)
- free(new->delay_queue);
- if (new->cluster_queue)
- free(new->cluster_queue);
- free(new);
- }
- return r;
}
static void abort_startup(struct clog_cpg *del)
@@ -1446,22 +1285,19 @@ static void abort_startup(struct clog_cpg *del)
SaNameT name;
SaAisErrorT rv;
SaCkptCheckpointHandleT h;
+ struct list_head *p, *n;
struct clog_tfr *tfr = NULL;
LOG_DBG("[%s] CPG teardown before checkpoint received",
SHORT_UUID(del->name.value));
- while ((tfr = queue_remove(del->startup_queue))) {
+ list_for_each_safe(p, n, &del->startup_list) {
+ list_del_init(p);
+ tfr = (struct clog_tfr *)p;
LOG_DBG("[%s] Ignoring request from %u: %s",
SHORT_UUID(del->name.value), tfr->originator,
_RQ_TYPE(tfr->request_type));
- queue_add(tfr, free_queue);
- }
-
- while ((tfr = queue_remove(del->delay_queue))) {
- LOG_DBG("[%s] Ignoring delayed request: %s",
- SHORT_UUID(del->name.value), _RQ_TYPE(tfr->request_type));
- queue_add(tfr, free_queue);
+ free(tfr);
}
len = snprintf((char *)(name.value), SA_MAX_NAME_LENGTH, "bitmaps_%s_%u",
@@ -1501,30 +1337,14 @@ unlink_retry:
static int _destroy_cluster_cpg(struct clog_cpg *del)
{
int r;
- struct clog_tfr *tfr;
- LOG_COND(log_resend_requests, "[%s] I am leaving (1).....",
+ LOG_COND(log_resend_requests, "[%s] I am leaving.2.....",
SHORT_UUID(del->name.value));
- tfr = queue_remove(free_queue);
- if (tfr) {
- tfr->request_type = DM_CLOG_MEMBER_LEAVE;
- tfr->originator = my_cluster_id;
- tfr->seq = 0;
- strncpy(tfr->uuid, del->name.value, CPG_MAX_NAME_LENGTH);
- r = cluster_send(tfr);
- if (r < 0)
- LOG_ERROR("[%s] Failed to send request to cluster: %s",
- SHORT_UUID(tfr->uuid), _RQ_TYPE(tfr->request_type));
- else if (!r)
- queue_add(tfr, free_queue);
- }
-
del->cpg_state = INVALID;
del->state = LEAVING;
- if (!queue_empty(del->startup_queue) ||
- !queue_empty(del->delay_queue))
+ if (!list_empty(&del->startup_list))
abort_startup(del);
r = cpg_leave(del->handle, &del->name);
diff --git a/cmirror/src/functions.c b/cmirror/src/functions.c
index c341d7f..59de0fe 100644
--- a/cmirror/src/functions.c
+++ b/cmirror/src/functions.c
@@ -10,8 +10,9 @@
#include <linux/kdev_t.h>
#define __USE_GNU /* for O_DIRECT */
#include <fcntl.h>
+#include "linux/dm-clog-tfr.h"
+#include "list.h"
#include "functions.h"
-#include "queues.h"
#include "common.h"
#include "cluster.h"
#include "logging.h"
@@ -530,10 +531,10 @@ static int clog_ctr(struct clog_tfr *tfr)
if (strlen(tfr->data) != tfr->data_size) {
LOG_ERROR("Received constructor request with bad data");
- LOG_DBG("strlen(tfr->data)[%d] != tfr->data_size[%d]",
- (int)strlen(tfr->data), tfr->data_size);
- LOG_DBG("tfr->data = '%s' [%d]",
- tfr->data, (int)strlen(tfr->data));
+ LOG_ERROR("strlen(tfr->data)[%d] != tfr->data_size[%d]",
+ (int)strlen(tfr->data), tfr->data_size);
+ LOG_ERROR("tfr->data = '%s' [%d]",
+ tfr->data, (int)strlen(tfr->data));
return -EINVAL;
}
diff --git a/cmirror/src/local.c b/cmirror/src/local.c
index 3e9c312..17c1c74 100644
--- a/cmirror/src/local.c
+++ b/cmirror/src/local.c
@@ -1,13 +1,14 @@
#include <unistd.h>
#include <errno.h>
#include <string.h>
+#include <stdint.h>
#include <sys/types.h>
#include <sys/socket.h>
#include <sys/poll.h>
#include <linux/connector.h>
#include <linux/netlink.h>
-#include "queues.h"
+#include "linux/dm-clog-tfr.h"
#include "functions.h"
#include "cluster.h"
#include "common.h"
@@ -16,6 +17,8 @@
#include "local.h"
static int cn_fd; /* Connector (netlink) socket fd */
+static char recv_buf[2048];
+
/* FIXME: merge this function with kernel_send_helper */
static int kernel_ack(uint32_t seq, int error)
@@ -60,6 +63,9 @@ static int kernel_ack(uint32_t seq, int error)
* Read requests from the kernel and allocate space for the new request.
* If there is no request from the kernel, *tfr is NULL.
*
+ * This function is not thread safe due to returned stack pointer. In fact,
+ * the returned pointer must not be in-use when this function is called again.
+ *
* Returns: 0 on success, -EXXX on error
*/
static int kernel_recv(struct clog_tfr **tfr)
@@ -67,38 +73,24 @@ static int kernel_recv(struct clog_tfr **tfr)
int r = 0;
int len;
struct cn_msg *msg;
- char buf[2048];
-
- /*
- * A failure to allocate space means the request is lost
- * The kernel must retry
- */
- if (!(*tfr = queue_remove(free_queue))) {
- LOG_PRINT("kernel_recv: Preallocated transfer structs exhausted");
- *tfr = malloc(DM_CLOG_TFR_SIZE);
- if (!*tfr) {
- LOG_ERROR("kernel_recv: Unable to allocate transfer struct");
- return -ENOMEM;
- }
- }
- memset(*tfr, 0, DM_CLOG_TFR_SIZE);
- memset(buf, 0, sizeof(buf));
+ *tfr = NULL;
+ memset(recv_buf, 0, sizeof(recv_buf));
- len = recv(cn_fd, buf, sizeof(buf), 0);
+ len = recv(cn_fd, recv_buf, sizeof(recv_buf), 0);
if (len < 0) {
LOG_ERROR("Failed to recv message from kernel");
r = -errno;
goto fail;
}
- switch (((struct nlmsghdr *)buf)->nlmsg_type) {
+ switch (((struct nlmsghdr *)recv_buf)->nlmsg_type) {
case NLMSG_ERROR:
LOG_ERROR("Unable to recv message from kernel: NLMSG_ERROR");
r = -EBADE;
goto fail;
case NLMSG_DONE:
- msg = (struct cn_msg *)NLMSG_DATA((struct nlmsghdr *)buf);
+ msg = (struct cn_msg *)NLMSG_DATA((struct nlmsghdr *)recv_buf);
len -= sizeof(struct nlmsghdr);
if (len < sizeof(struct cn_msg)) {
@@ -122,8 +114,8 @@ static int kernel_recv(struct clog_tfr **tfr)
if (len < msg->len)
LOG_ERROR("len = %d, msg->len = %d", len, msg->len);
- memcpy(*tfr, msg->data, msg->len);
- INIT_LIST_HEAD((struct list_head *)&((*tfr)->private));
+ msg->data[msg->len] = '\0'; /* Cleaner way to ensure this? */
+ *tfr = (struct clog_tfr *)msg->data;
if (!(*tfr)->request_type) {
LOG_DBG("Bad transmission, requesting resend [%u]", msg->seq);
@@ -142,10 +134,8 @@ static int kernel_recv(struct clog_tfr **tfr)
}
fail:
- if (r) {
- queue_add(*tfr, free_queue);
+ if (r)
*tfr = NULL;
- }
return (r == -EAGAIN) ? 0 : r;
}
@@ -225,20 +215,6 @@ static int do_local_work(void *data)
RQ_TYPE(tfr->request_type));
break;
- case DM_CLOG_POSTSUSPEND:
- /* We do not specify ourselves as server here */
- r = do_request(tfr, 0);
- if (r) {
- LOG_DBG("Returning failed request to kernel [%s]",
- RQ_TYPE(tfr->request_type));
- r = kernel_send(tfr);
- if (r)
- LOG_ERROR("Failed to respond to kernel [%s]",
- RQ_TYPE(tfr->request_type));
- }
- queue_add_tail(tfr, cluster_queue);
-
- break;
case DM_CLOG_RESUME:
/*
* Resume is a special case that requires a local
@@ -262,21 +238,15 @@ static int do_local_work(void *data)
case DM_CLOG_GET_RESYNC_WORK:
case DM_CLOG_SET_REGION_SYNC:
case DM_CLOG_IS_REMOTE_RECOVERING:
+ case DM_CLOG_POSTSUSPEND:
r = cluster_send(tfr);
- if (r < 0) {
+ if (r) {
LOG_ERROR("[%s] Unable to send %s to cluster: %s",
SHORT_UUID(tfr->uuid),
RQ_TYPE(tfr->request_type), strerror(-r));
tfr->data_size = 0;
tfr->error = r;
kernel_send(tfr);
- } else if (!r) {
- /*
- * If this was multi-threaded, we would have to
- * add the 'tfr' to the queue before doing
- * the cluster_send
- */
- queue_add_tail(tfr, cluster_queue);
}
break;
@@ -284,7 +254,7 @@ static int do_local_work(void *data)
r = kernel_ack(tfr->seq, 0);
r = cluster_send(tfr);
- if (r < 0) {
+ if (r) {
LOG_ERROR("[%s] Unable to send %s to cluster: %s",
SHORT_UUID(tfr->uuid),
RQ_TYPE(tfr->request_type), strerror(-r));
@@ -293,18 +263,16 @@ static int do_local_work(void *data)
* This would allow us to optimize MARK_REGION
* too.
*/
- } else if (!r)
- queue_add_tail(tfr, free_queue);
+ }
break;
case DM_CLOG_GET_REGION_SIZE:
default:
LOG_ERROR("Invalid log request received, ignoring.");
- queue_add_tail(tfr, free_queue);
return 0;
}
- if ((r < 0) && !tfr->error) {
+ if (r && !tfr->error) {
LOG_ERROR("Programmer error: tfr->error not set.");
tfr->error = r;
}
@@ -358,8 +326,6 @@ int kernel_send(struct clog_tfr *tfr)
if (r)
LOG_ERROR("Failed to send msg to kernel.");
- queue_add(tfr, free_queue);
-
return r;
}
diff --git a/cmirror/src/queues.c b/cmirror/src/queues.c
deleted file mode 100644
index 5668bdc..0000000
--- a/cmirror/src/queues.c
+++ /dev/null
@@ -1,239 +0,0 @@
-#include <stdio.h>
-#include <errno.h>
-
-#include <string.h>
-
-#include "queues.h"
-#include "common.h"
-#include "logging.h"
-
-struct queue *cluster_queue;
-struct queue *free_queue;
-
-#define WHICH_QUEUE(q) \
- (q == cluster_queue) ? "cluster_queue" : \
- (q == free_queue) ? "free_queue" : "<unknown queue>"
-
-/*
- * queue_dtr
- * @q: queue to destroy
- *
- * Free the queue and all its contents
- */
-static void queue_dtr(struct queue *q)
-{
- struct list_head *p, *n;
- struct clog_tfr *tfr;
-
- if (!q)
- return;
-
- if (q->count && (q != free_queue))
- LOG_ERROR("WARNING: There are still items in %s\n",
- WHICH_QUEUE(q));
-
- list_for_each_safe(p, n, &q->list) {
- tfr = (struct clog_tfr *)p;
- list_del_init(p);
- free(tfr);
- }
-
- free(q);
-}
-
-/*
- * queue_ctr
- * @q: location of new queue
- * @count: number of 'struct clog_tfr's to pre-allocate
- *
- * A queue is initialized and populated with the
- * specified amount of 'struct clog_tfr's.
- *
- * Returns: 0 on success, -EXXX on failure
- */
-static int queue_ctr(struct queue **q, int count)
-{
- int i;
- struct queue *tmp;
- struct clog_tfr *tfr;
-
- *q = NULL;
- tmp = malloc(sizeof(struct queue));
- if (!tmp)
- return -ENOMEM;;
-
- INIT_LIST_HEAD(&(tmp->list));
- tmp->count = 0;
-
- for (i = 0; i < count; i++) {
- tfr = malloc(DM_CLOG_TFR_SIZE);
- if (!tfr) {
- queue_dtr(tmp);
- return -ENOMEM;
- }
- list_add((struct list_head *)&tfr->private, &tmp->list);
- tmp->count++;
- }
-
- *q = tmp;
- return 0;
-}
-
-int queue_status(int output_wanted)
-{
- int i=1;
- struct clog_tfr *tfr;
- struct list_head *p, *n;
-
- if (output_wanted) {
- LOG_PRINT("cluster_queue: %d", cluster_queue->count);
- list_for_each_safe(p, n, &cluster_queue->list) {
- tfr = (struct clog_tfr *)p;
- LOG_PRINT(" %d) %s, originator = %u",
- i++, RQ_TYPE(tfr->request_type),
- tfr->originator);
- }
-
- LOG_PRINT("free_queue : %d", free_queue->count);
- }
-
- return cluster_queue->count;
-}
-
-/*
- * init_queues
- *
- * Initialize queues.
- *
- * Returns: 0 on success, values from common.h on failure
- */
-int init_queues(void)
-{
- int r;
-
- cluster_queue = free_queue = NULL;
-
- if ((r = queue_ctr(&cluster_queue, 0)) ||
- (r = queue_ctr(&free_queue, 100))) {
- if (cluster_queue)
- queue_dtr(cluster_queue);
-
- return EXIT_QUEUE_NOMEM;
- }
-
- return 0;
-}
-
-/*
- * cleanup_queues
- *
- * Clean up before exiting
- */
-void cleanup_queues(void)
-{
- queue_dtr(cluster_queue);
- queue_dtr(free_queue);
-}
-
-/*
- * queue_add_tail
- * @tfr: item to add
- * @q: receiving queue
- *
- * Perform necessary locking and add item to queue.
- */
-void queue_add_tail(struct clog_tfr *tfr, struct queue *q)
-{
- q->count++;
- list_add_tail((struct list_head *)&tfr->private, &(q->list));
-}
-
-/*
- * queue_add
- * @tfr: item to add
- * @q: receiving queue
- *
- * Perform necessary locking and add item to front of queue.
- */
-void queue_add(struct clog_tfr *tfr, struct queue *q)
-{
- q->count++;
- list_add((struct list_head *)&tfr->private, &(q->list));
-}
-
-/*
- * queue_remove
- * @q: queue to remove an item from
- *
- * Perform necessary locking and pull first item
- * out of the queue.
- *
- * Returns: NULL if empty, item otherwise
- */
-struct clog_tfr *queue_remove(struct queue *q)
-{
- struct clog_tfr *tfr;
-
- if (list_empty(&q->list))
- return NULL;
-
- tfr = (struct clog_tfr *)q->list.next;
- list_del_init((struct list_head *)&tfr->private);
- q->count--;
-
- return tfr;
-}
-
-/*
- * queue_remove_match
- * @q: queue to remove an item from
- * @tfr_cmp: the struct clog_tfr to use as comparison
- * @f: function used for matching
- *
- * Perform necessary locking and pull first item
- * out of the queue that causes the function
- * executed to return true.
- *
- * Returns: NULL if not found, item otherwise
- */
-struct clog_tfr *queue_remove_match(struct queue *q,
- int (*f)(struct clog_tfr *, struct clog_tfr *),
- struct clog_tfr *tfr_cmp)
-{
- struct clog_tfr *tfr;
- struct list_head *p, *n;
-
- if (list_empty(&q->list))
- return NULL;
-
- list_for_each_safe(p, n, &q->list) {
- tfr = (struct clog_tfr *)p;
- if (f(tfr, tfr_cmp)) {
- list_del_init(p);
- q->count--;
-
- return tfr;
- }
- }
-
- return NULL;
-}
-
-/*
- * queue_remove_all
- * @l: list_head to populate with entire queue contents
- * @q: queue to remove items from
- *
- * Perform necessary locking and return the entire contents
- * of the queue into the supplied list_head.
- */
-void queue_remove_all(struct list_head *l, struct queue *q)
-{
- list_splice_init(&q->list, l);
- q->count = 0;
-}
-
-int queue_empty(struct queue *q)
-{
- return q->count ? 0: 1;
-}
diff --git a/cmirror/src/queues.h b/cmirror/src/queues.h
deleted file mode 100644
index 509c25a..0000000
--- a/cmirror/src/queues.h
+++ /dev/null
@@ -1,30 +0,0 @@
-#ifndef __CLUSTER_LOG_QUEUES_DOT_H__
-#define __CLUSTER_LOG_QUEUES_DOT_H__
-
-#include <stdlib.h>
-#include <stdint.h>
-#include "linux/dm-clog-tfr.h"
-#include "./list.h"
-
-struct queue {
- /* pthread lock */
- int count;
- struct list_head list;
-};
-
-extern struct queue *cluster_queue;
-extern struct queue *free_queue;
-
-int init_queues(void);
-void cleanup_queues(void);
-int queue_status(int);
-void queue_add_tail(struct clog_tfr *tfr, struct queue *q);
-void queue_add(struct clog_tfr *tfr, struct queue *q);
-struct clog_tfr *queue_remove(struct queue *q);
-struct clog_tfr *queue_remove_match(struct queue *q,
- int (*f)(struct clog_tfr *, struct clog_tfr *),
- struct clog_tfr *tfr_cmp);
-void queue_remove_all(struct list_head *l, struct queue *q);
-int queue_empty(struct queue *q);
-
-#endif /* __CLUSTER_LOG_QUEUES_DOT_H__ */
diff --git a/cmirror/src/rbtree.c b/cmirror/src/rbtree.c
deleted file mode 100644
index e76cc0a..0000000
--- a/cmirror/src/rbtree.c
+++ /dev/null
@@ -1,479 +0,0 @@
-#include <stdio.h>
-#include <stdlib.h>
-#include <stdint.h>
-#include <errno.h>
-#include <string.h>
-#include "logging.h"
-#include "rbtree.h"
-
-#define RED 1
-#define BLACK 0
-
-#define RIGHT(x) (x)->rb_right
-#define LEFT(x) (x)->rb_left
-#define PARENT(x) (x)->rb_parent
-#define COLOR(x) (x)->rb_color
-
-#define NIL(x) (&(x)->null_node)
-#define ROOT(x) ((x)->root)
-
-#define KEY(x) (t->get_key(x->rb_data))
-
-#define EQ_NODES(t, x, y) (t->cmp_keys(KEY(x), KEY(y)) == 0)
-#define LT_NODES(t, x, y) (t->cmp_keys(KEY(x), KEY(y)) < 0)
-#define GT_NODES(t, x, y) (t->cmp_keys(KEY(x), KEY(y)) > 0)
-
-#define EQ_KEYS(t, x, y) (t->cmp_keys(x, y) == 0)
-#define LT_KEYS(t, x, y) (t->cmp_keys(x, y) < 0)
-#define GT_KEYS(t, x, y) (t->cmp_keys(x, y) > 0)
-
-int rbt_init(struct rb_tree *t, int data_size,
- void *(*get_key)(void *data),
- int (*cmp_keys)(void *a, void *b))
-{
- if (!t) {
- errno = EINVAL;
- return -1;
- }
-
- memset(t, 0, sizeof(struct rb_tree));
-
- t->data_size = data_size;
- COLOR(NIL(t)) = BLACK;
- ROOT(t) = NIL(t);
- t->get_key = get_key;
- t->cmp_keys = cmp_keys;
-
- return 0;
-}
-
-static struct rb_node *left_rotate(struct rb_tree *t, struct rb_node *axis)
-{
- struct rb_node *tmp;
-
- if (RIGHT(axis) == NIL(t)) {
- LOG_ERROR("Tree error: unable to left rotate");
- return axis;
- }
-
- LOG_DBG("TREE[0x%p]: left_rotate [axis = %llu]",
- t, (unsigned long long)*((uint64_t *)KEY(axis)));
- tmp = RIGHT(axis);
- RIGHT(axis) = LEFT(tmp);
- if (LEFT(tmp) != NIL(t))
- PARENT(LEFT(tmp)) = axis;
-
- PARENT(tmp) = PARENT(axis);
-
- if (PARENT(axis) == NIL(t))
- ROOT(t) = tmp;
- else if (axis == LEFT(PARENT(axis)))
- LEFT(PARENT(axis)) = tmp;
- else
- RIGHT(PARENT(axis)) = tmp;
-
- LEFT(tmp) = axis;
- PARENT(axis) = tmp;
- return tmp;
-}
-
-static struct rb_node *right_rotate(struct rb_tree *t, struct rb_node *axis)
-{
- struct rb_node *tmp;
-
- if (LEFT(axis) == NIL(t)) {
- LOG_ERROR("Tree error: unable to right rotate");
- return axis;
- }
-
- LOG_DBG("TREE[0x%p]: right_rotate [axis = %llu]",
- t, (unsigned long long)*((uint64_t *)KEY(axis)));
- tmp = LEFT(axis);
- LEFT(axis) = RIGHT(tmp);
- if (RIGHT(tmp) != NIL(t))
- PARENT(RIGHT(tmp)) = axis;
-
- PARENT(tmp) = PARENT(axis);
-
- if (PARENT(axis) == NIL(t))
- ROOT(t) = tmp;
- else if (axis == RIGHT(PARENT(axis)))
- RIGHT(PARENT(axis)) = tmp;
- else
- LEFT(PARENT(axis)) = tmp;
-
- RIGHT(tmp) = axis;
- PARENT(axis) = tmp;
- return tmp;
-}
-
-static int _insert(struct rb_tree *t, struct rb_node *new)
-{
- struct rb_node *x = ROOT(t), *y = NIL(t);
-
- x = ROOT(t);
- y = NIL(t);
- RIGHT(new) = LEFT(new) = PARENT(new) = NIL(t);
-
- while (x != NIL(t)) {
- y = x;
- if (LT_NODES(t, new, x))
- x = LEFT(x);
- else
- x = RIGHT(x);
- }
-
- PARENT(new) = y;
-
- if (y == NIL(t))
- ROOT(t) = new;
- else if (LT_NODES(t, new, y))
- LEFT(y) = new;
- else
- RIGHT(y) = new;
-
- return 0;
-}
-
-struct rb_node *rbt_alloc_node(struct rb_tree *t)
-{
- struct rb_node *new;
-
- t->in_use_nodes++;
- if (t->in_use_nodes > t->max_nodes) {
- t->max_nodes = t->in_use_nodes;
- LOG_PRINT("TREE[0x%p]: Maximum tree nodes now at %d",
- t, t->max_nodes);
- }
-
- LOG_DBG("TREE[0x%p]: allocating node (in_use_nodes = %d, max_nodes = %d)",
- t, t->in_use_nodes, t->max_nodes);
-
- if (t->free_list) {
- new = t->free_list;
- t->free_list = new->rb_next;
- return new;
- }
-
- new = malloc(sizeof(*new) + t->data_size);
- new->rb_data = new + 1;
-
- return new;
-}
-
-void rbt_free_node(struct rb_tree *t, struct rb_node *d)
-{
- t->in_use_nodes--;
-
- d->rb_next = t->free_list;
- t->free_list = d;
-
- LOG_DBG("TREE[0x%p]: freeing node (in_use_nodes = %d, max_nodes = %d)",
- t, t->in_use_nodes, t->max_nodes);
-
- /* FIXME: We never free any nodes */
-}
-
-int rbt_insert(struct rb_tree *t, struct rb_node *new)
-{
- struct rb_node *tmp;
-
- LOG_DBG("TREE[0x%p]: inserting %llu",
- t, (unsigned long long)*((uint64_t *)KEY(new)));
- if (!t || !new) {
- errno = EINVAL;
- return -1;
- }
-
- if (_insert(t, new))
- return -1;
-
- COLOR(new) = RED;
-
- while ((new != ROOT(t)) && (COLOR(PARENT(new)) == RED)) {
- if (PARENT(new) == LEFT(PARENT(PARENT(new)))) {
- tmp = RIGHT(PARENT(PARENT(new)));
- if (COLOR(tmp) == RED) {
- COLOR(PARENT(new)) = BLACK;
- COLOR(tmp) = BLACK;
- COLOR(PARENT(PARENT(new))) = RED;
- new = PARENT(PARENT(new));
- } else {
- if (new == RIGHT(PARENT(new))) {
- new = PARENT(new);
- left_rotate(t, new);
- }
- COLOR(PARENT(new)) = BLACK;
- COLOR(PARENT(PARENT(new))) = RED;
- right_rotate(t, PARENT(PARENT(new)));
- }
- } else {
- tmp = LEFT(PARENT(PARENT(new)));
- if (COLOR(tmp) == RED) {
- COLOR(PARENT(new)) = BLACK;
- COLOR(tmp) = BLACK;
- COLOR(PARENT(PARENT(new))) = RED;
- new = PARENT(PARENT(new));
- } else {
- if (new == LEFT(PARENT(new))) {
- new = PARENT(new);
- right_rotate(t, new);
- }
- COLOR(PARENT(new)) = BLACK;
- COLOR(PARENT(PARENT(new))) = RED;
- left_rotate(t, PARENT(PARENT(new)));
- }
- }
- }
- COLOR(ROOT(t)) = BLACK;
-
- return 0;
-}
-
-static int rbt_remove_fixup(struct rb_tree *t, struct rb_node *x)
-{
- struct rb_node *w;
-
- while ((x != ROOT(t)) && (COLOR(x) == BLACK)) {
- if (x == LEFT(PARENT(x))) {
- w = RIGHT(PARENT(x));
- if (COLOR(w) == RED) {
- COLOR(w) = BLACK;
- COLOR(PARENT(x)) = RED;
- left_rotate(t, PARENT(x));
- w = RIGHT(PARENT(x));
- }
-
- if ((COLOR(LEFT(w)) == BLACK) && (COLOR(RIGHT(w)) == BLACK)) {
- COLOR(w) = RED;
- x = PARENT(x);
- } else {
- if (COLOR(RIGHT(w)) == BLACK) {
- COLOR(LEFT(w)) = BLACK;
- COLOR(w) = RED;
- right_rotate(t, w);
- w = RIGHT(PARENT(x));
- }
- COLOR(w) = COLOR(PARENT(x));
- COLOR(PARENT(x)) = BLACK;
- COLOR(RIGHT(w)) = BLACK;
- left_rotate(t, PARENT(x));
- x = ROOT(t);
- }
- } else {
- w = LEFT(PARENT(x));
- if (COLOR(w) == RED) {
- COLOR(w) = BLACK;
- COLOR(PARENT(x)) = RED;
- right_rotate(t, PARENT(x));
- w = LEFT(PARENT(x));
- }
- if ((COLOR(RIGHT(w)) == BLACK) && (COLOR(LEFT(w)) == BLACK)) {
- COLOR(w) = RED;
- x = PARENT(x);
- } else {
- if (COLOR(LEFT(w)) == BLACK) {
- COLOR(RIGHT(w)) = BLACK;
- COLOR(w) = RED;
- left_rotate(t, w);
- w = LEFT(PARENT(x));
- }
- COLOR(w) = COLOR(PARENT(x));
- COLOR(PARENT(x)) = BLACK;
- COLOR(LEFT(w)) = BLACK;
- right_rotate(t, PARENT(x));
- x = ROOT(t);
- }
- }
- }
-
- COLOR(x) = BLACK;
- return 0;
-}
-
-static struct rb_node *rbt_minimum(struct rb_tree *t, struct rb_node *x)
-{
- while (LEFT(x) != NIL(t))
- x = LEFT(x);
-
- return x;
-}
-
-static struct rb_node *rbt_successor(struct rb_tree *t, struct rb_node *x)
-{
- struct rb_node *y;
- if (RIGHT(x) != NIL(t))
- return rbt_minimum(t, RIGHT(x));
-
- y = PARENT(x);
-
- while ((y != NIL(t)) && (x == RIGHT(y))) {
- x = y;
- y = PARENT(y);
- }
-
- return y;
-}
-
-int rbt_remove(struct rb_tree *t, struct rb_node *del)
-{
- struct rb_node *x, *y;
-
- LOG_DBG("TREE[0x%p]: removing %llu",
- t, (unsigned long long)*((uint64_t *)KEY(del)));
- if ((LEFT(del) == NIL(t)) || (RIGHT(del) == NIL(t)))
- y = del;
- else
- y = rbt_successor(t, del);
-
- if (LEFT(y) != NIL(t))
- x = LEFT(y);
- else
- x = RIGHT(y);
-
- PARENT(x) = PARENT(y);
-
- if (PARENT(y) == NIL(t))
- ROOT(t) = x;
- else if (y == LEFT(PARENT(y)))
- LEFT(PARENT(y)) = x;
- else
- RIGHT(PARENT(y)) = x;
-
- if (y != del)
- memcpy(del->rb_data, y->rb_data, t->data_size);
-
- if (COLOR(y) == BLACK)
- rbt_remove_fixup(t, x);
-
- return 0;
-}
-
-struct rb_node *rbt_first(struct rb_tree *t)
-{
- struct rb_node *x;
-
- if (!t || ROOT(t) == NIL(t))
- return NULL;
-
- for(x = ROOT(t); LEFT(x) != NIL(t); x = LEFT(x));
-
- return x;
-}
-
-static struct rb_node *_rbt_walk(struct rb_tree *t, struct rb_node *x, struct rb_node **list,
- int (*additional_test)(void *data, void *adata),
- void *additional_data)
-{
- if (!x || x == NIL(t))
- return NULL;
-
- _rbt_walk(t, RIGHT(x), list, additional_test, additional_data);
- if (!additional_test || additional_test(x->rb_data, additional_data)) {
- if (*list) {
- x->rb_next = *list;
- *list = x;
- } else {
- *list = x;
- x->rb_next = NULL;
- }
- }
-
- _rbt_walk(t, LEFT(x), list, additional_test, additional_data);
-
- return *list;
-}
-
-struct rb_node *rbt_walk(struct rb_tree *t)
-{
- struct rb_node *list= NULL;
-
- if (!t || !ROOT(t)) {
- errno = EINVAL;
- return NULL;
- }
- errno = 0;
- if (ROOT(t) == NIL(t))
- return NULL;
-
- return _rbt_walk(t, ROOT(t), &list, NULL, NULL);
-}
-
-struct rb_node *rbt_walk_plus(struct rb_tree *t,
- int (*additional_test)(void *data, void *adata),
- void *additional_data)
-{
- struct rb_node *list= NULL;
-
- if (!t || !ROOT(t)) {
- errno = EINVAL;
- return NULL;
- }
- errno = 0;
- if (ROOT(t) == NIL(t))
- return NULL;
-
- return _rbt_walk(t, ROOT(t), &list, additional_test, additional_data);
-}
-
-struct rb_node *_rbt_search(struct rb_tree *t, struct rb_node *x, void *key, struct rb_node **list,
- int (*additional_test)(void *data, void *adata),
- void *additional_data)
-{
- if (!x || x == NIL(t))
- return NULL;
-
- if (EQ_KEYS(t, KEY(x), key)) {
- if ((LEFT(x) != NIL(t)) && EQ_KEYS(t, KEY(LEFT(x)), key))
- _rbt_search(t, LEFT(x), key, list, additional_test, additional_data);
-
- if (!additional_test || additional_test(x->rb_data, additional_data)) {
- if (*list) {
- x->rb_next = *list;
- *list = x;
- } else {
- *list = x;
- x->rb_next = NULL;
- }
- }
- _rbt_search(t, RIGHT(x), key, list, additional_test, additional_data);
- return *list;
- } else if (LT_KEYS(t, key, KEY(x)))
- return _rbt_search(t, LEFT(x), key, list, additional_test, additional_data);
-
- return _rbt_search(t, RIGHT(x), key, list, additional_test, additional_data);
-}
-
-struct rb_node *rbt_search(struct rb_tree *t, void *key)
-{
- struct rb_node *list = NULL;
-
- if (!t || !ROOT(t)) {
- errno = EINVAL;
- return NULL;
- }
-
- errno = 0;
- if (ROOT(t) == NIL(t))
- return NULL;
-
- return _rbt_search(t, ROOT(t), key, &list, NULL, NULL);
-}
-
-struct rb_node *rbt_search_plus(struct rb_tree *t, void *key,
- int (*additional_test)(void *data, void *adata),
- void *additional_data)
-{
- struct rb_node *list = NULL;
-
- if (!t || !ROOT(t)) {
- errno = EINVAL;
- return NULL;
- }
-
- errno = 0;
- if (ROOT(t) == NIL(t))
- return NULL;
-
- return _rbt_search(t, ROOT(t), key, &list, additional_test, additional_data);
-}
diff --git a/cmirror/src/rbtree.h b/cmirror/src/rbtree.h
deleted file mode 100644
index 390e1ea..0000000
--- a/cmirror/src/rbtree.h
+++ /dev/null
@@ -1,64 +0,0 @@
-#ifndef __RBTREE_H__
-#define __RBTREE_H__
-
-struct rb_node {
- int rb_color;
- struct rb_node *rb_parent;
- struct rb_node *rb_left;
- struct rb_node *rb_right;
- struct rb_node *rb_next; /* for returning lists */
- void *rb_data;
-};
-
-struct rb_tree {
- int data_size;
-
- /* Next to fields for debugging, should be removed */
- int in_use_nodes;
- int max_nodes;
-
- struct rb_node *root;
- struct rb_node null_node;
-
- struct rb_node *free_list;
-
- void *(*get_key)(void *data);
- int (*cmp_keys)(void *a, void *b);
-};
-
-int rbt_init(struct rb_tree *t, int data_size,
- void *(*get_key)(void *data),
- int (*cmp_keys)(void *a, void *b));
-
-struct rb_node *rbt_alloc_node(struct rb_tree *t);
-void rbt_free_node(struct rb_tree *t, struct rb_node *d);
-
-int rbt_insert(struct rb_tree *t, struct rb_node *new);
-int rbt_remove(struct rb_tree *t, struct rb_node *del);
-
-struct rb_node *rbt_first(struct rb_tree *t);
-struct rb_node *rbt_first_plus(struct rb_tree *t,
- int (*additional_test)(void *data, void *adata),
- void *additional_data);
-
-struct rb_node *rbt_next(struct rb_tree *t, struct rb_node *n);
-struct rb_node *rbt_next_plus(struct rb_tree *t, struct rb_node *n,
- int (*additional_test)(void *data, void *adata),
- void *additional_data);
-
-struct rb_node *rbt_walk(struct rb_tree *t);
-struct rb_node *rbt_walk_plus(struct rb_tree *t,
- int (*additional_test)(void *data, void *adata),
- void *additional_data);
-
-struct rb_node *rbt_search(struct rb_tree *t, void *key);
-struct rb_node *rbt_search_plus(struct rb_tree *t, void *key,
- int (*additional_test)(void *data, void *adata),
- void *additional_data);
-
-struct rb_node *rbt_search_from(struct rb_tree *t, struct rb_node *n, void *key);
-struct rb_node *rbt_search_from_plus(struct rb_tree *t, struct rb_node *n, void *key,
- int (*additional_test)(void *data, void *adata),
- void *additional_data);
-
-#endif /* __RBTREE_H__ */