| Newsgroups |
gmane.network.spread.cvs |
| Message-ID |
<[email protected]> |
Author: jschultz
Date: 2005-07-28 10:50:56 -0400 (Thu, 28 Jul 2005)
New Revision: 252
Modified:
trunk/daemon/groups.c
trunk/daemon/sess_body.h
Log:
Removed iterators from sess_body.h structures and insert/removals. Changed all skiplist's to function as unique key sets (i.e. - no values): this requires that the members used for key comparison in the referenced structs are the first members of those structs. Changed grp->mboxes to be an unsorted dynamic array (stdarr). Changed G-analize_groups to be more like it was before, but I "upgraded" it a bit, it should be slightly faster now than before. Added some comments for clarity and potential future work in TODO and FIXME comments.
Modified: trunk/daemon/groups.c
===================================================================
--- trunk/daemon/groups.c 2005-07-22 08:40:34 UTC (rev 251)
+++ trunk/daemon/groups.c 2005-07-28 14:50:56 UTC (rev 252)
@@ -123,7 +123,9 @@
static int Groups_control_down_queue;
-static stdskl GroupsList; /* (char*) -> (group*) */
+static stdskl GroupsList; /* (group*) -> nil */
+/* TODO: might want to add a "secondary" index of daemon IDs -> groups for potentially faster performance */
+/* TODO: might want to add a "secondary" index of member IDs -> groups for potentially faster performance */
static synced_set MySyncedSet;
static membership_id unknown_memb_id = { -1, -1 }; /* See explanation above. */
@@ -167,6 +169,7 @@
static int G_check_if_changed_by_cascade( group *grp );
static void G_remove_daemon( group *grp, daemon_members *dmn );
static void G_remove_group( group *grp );
+static void G_remove_mailbox( group *grp, mailbox m );
static int G_compare_cstrptr(const void *, const void *);
static int G_compare_proc_ids_by_conf( const void *, const void * );
@@ -183,8 +186,8 @@
static int G_compare_proc_ids_by_conf(const void *a, const void *b)
{
proc dummy_proc;
- int ia = Conf_proc_by_id( *(const int32*) a, &dummy_proc );
- int ib = Conf_proc_by_id( *(const int32*) b, &dummy_proc );
+ int ia = Conf_proc_by_id( **(const int32**) a, &dummy_proc );
+ int ib = Conf_proc_by_id( **(const int32**) b, &dummy_proc );
assert( ia > -1 );
assert( ib > -1 );
@@ -236,7 +239,7 @@
MySyncedSet.proc_ids[0] = My.id;
G_print_synced_set( SPLOG_INFO, &MySyncedSet, "G_init" );
- ret = stdskl_construct(&GroupsList, sizeof(char*), sizeof(group*), G_compare_cstrptr);
+ ret = stdskl_construct(&GroupsList, sizeof(group*), 0, G_compare_cstrptr);
if (ret != 0) {
Alarmp( SPLOG_FATAL, GROUPS, "G_init: Failure to Initialize GroupsList\n");
}
@@ -334,7 +337,7 @@
{
for (stdskl_begin(&GroupsList, &it); !stdskl_is_end(&GroupsList, &it); )
{
- grp = *(group**) stdskl_it_val(&it);
+ grp = *(group**) stdskl_it_key(&it);
stdskl_it_next(&it); /* NOTE: need to do advancement before potential erasure below */
if( grp->changed )
@@ -358,7 +361,7 @@
grp->changed = 0;
G_print_group_id( SPLOG_DEBUG, grp->grp_id, "G_handle_reg_memb" );
G_update_daemon_memb_ids( grp );
- if( !stdskl_empty(&grp->mboxes) )
+ if( !stdarr_empty(&grp->mboxes) )
{
G_send_heavyweight_memb( grp );
}
@@ -385,7 +388,7 @@
for (stdskl_begin(&GroupsList, &it); !stdskl_is_end(&GroupsList, &it); )
{
- grp = *(group**) stdskl_it_val(&it);
+ grp = *(group**) stdskl_it_key(&it);
stdskl_it_next(&it); /* NOTE: need to do advancement before potential erasure below */
if( grp->changed )
@@ -487,7 +490,7 @@
*/
for (stdskl_begin(&GroupsList, &it); !stdskl_is_end(&GroupsList, &it); )
{
- grp = *(group**) stdskl_it_val(&it);
+ grp = *(group**) stdskl_it_key(&it);
stdskl_it_next(&it); /* NOTE: need to do advancement before potential erasure below */
group_changed = G_eliminate_partitioned_daemons( grp );
@@ -565,14 +568,14 @@
for (stdskl_begin(&GroupsList, &git); !stdskl_is_end(&GroupsList, &git); )
{
- grp = *(group**) stdskl_it_val(&git);
+ grp = *(group**) stdskl_it_key(&git);
stdskl_it_next(&git); /* NOTE: need to do advancement before potential erasure below */
group_changed = 0;
for (stdskl_begin(&grp->DaemonsList, &dit); !stdskl_is_end(&grp->DaemonsList, &dit); )
{
- dmn = *(daemon_members**) stdskl_it_val(&dit);
+ dmn = *(daemon_members**) stdskl_it_key(&dit);
stdskl_it_next(&dit); /* NOTE: need to do advancement before potential erasure below */
if( Conf_id_in_conf( &Trans_memb, dmn->proc_id ) == -1 )
@@ -584,7 +587,7 @@
}
if( group_changed )
{
- if( !stdskl_empty(&grp->mboxes) )
+ if( !stdarr_empty(&grp->mboxes) )
{
G_send_trans_memb( grp );
}
@@ -649,7 +652,7 @@
for (stdskl_begin(&GroupsList, &git); !stdskl_is_end(&GroupsList, &git); )
{
- grp = *(group**) stdskl_it_val(&git);
+ grp = *(group**) stdskl_it_key(&git);
stdskl_it_next(&git); /* NOTE: need to do advancement before potential erasure below */
group_changed = G_check_if_changed_by_cascade( grp );
@@ -733,11 +736,11 @@
memset( new_grp->name, 0, MAX_GROUP_NAME );
strcpy( new_grp->name, group_name );
- if (stdskl_construct(&new_grp->DaemonsList, sizeof(int32), sizeof(daemon_members*), G_compare_proc_ids_by_conf) != 0) {
+ if (stdskl_construct(&new_grp->DaemonsList, sizeof(daemon_members*), 0, G_compare_proc_ids_by_conf) != 0) {
Alarmp( SPLOG_FATAL, GROUPS, "%s: %d: memory allocation failed\n", __FILE__, __LINE__ );
}
- if (stdskl_construct(&new_grp->mboxes, sizeof(mailbox), 0, NULL) != 0) {
+ if (stdarr_construct(&new_grp->mboxes, sizeof(mailbox), 0) != 0) {
Alarmp( SPLOG_FATAL, GROUPS, "%s: %d: memory allocation failed\n", __FILE__, __LINE__ );
}
@@ -757,7 +760,7 @@
new_grp->num_members = 0;
- if (stdskl_insert(&GroupsList, &new_grp->GroupsListIt, &new_grp->name, &new_grp, STDFALSE) != 0) {
+ if (stdskl_put(&GroupsList, NULL, &new_grp, NULL, STDFALSE) != 0) {
Alarmp( SPLOG_FATAL, GROUPS, "%s: %d: memory allocation failed\n", __FILE__, __LINE__ );
}
@@ -782,7 +785,7 @@
new_dmn->memb_id = unknown_memb_id;
}
- if (stdskl_insert(&grp->DaemonsList, &new_dmn->DaemonsListIt, &new_dmn->proc_id, &new_dmn, STDFALSE) != 0) {
+ if (stdskl_put(&grp->DaemonsList, NULL, &new_dmn, NULL, STDFALSE) != 0) {
Alarmp( SPLOG_FATAL, GROUPS, "%s: %d: memory allocation failed\n", __FILE__, __LINE__ );
}
@@ -801,7 +804,7 @@
memset( new_mbr->name, 0, MAX_GROUP_NAME );
strcpy( new_mbr->name, private_group_name );
- if (stdskl_insert(&dmn->MembersList, &new_mbr->MembersListIt, &new_mbr, NULL, STDFALSE) != 0) {
+ if (stdskl_put(&dmn->MembersList, NULL, &new_mbr, NULL, STDFALSE) != 0) {
Alarmp( SPLOG_FATAL, GROUPS, "%s: %d: memory allocation failed\n", __FILE__, __LINE__ );
}
@@ -816,7 +819,11 @@
new_mbox = Sessions[ ses ].mbox;
- if (stdskl_put(&grp->mboxes, NULL, &new_mbox, NULL, STDFALSE) != 0) {
+ /* TODO: do we need to ensure the insert is
+ unique or is that externally implied? Seems
+ to be implied by above checks. */
+
+ if (stdarr_push_back(&grp->mboxes, &new_mbox) != 0) {
Alarmp( SPLOG_FATAL, GROUPS, "%s: %d: memory allocation failed\n", __FILE__, __LINE__ );
}
} else
@@ -825,7 +832,7 @@
if( Is_partitioned_daemon( dmn ) && !grp->changed )
grp->changed = 1;
- if( !stdskl_empty(&grp->mboxes) ) {
+ if( !stdarr_empty(&grp->mboxes) ) {
if( grp->changed )
{
G_send_heavyweight_join( grp, new_mbr, new_mbox );
@@ -864,6 +871,7 @@
group *grp;
daemon_members *dmn;
member *mbr;
+ stdit it;
Alarmp( SPLOG_INFO, GROUPS, "G_handle_leave: %s leaves group %s\n", private_group_name, group_name );
@@ -920,18 +928,29 @@
if( p.id == My.id )
{
- /* notify this local member and extract its mbox from group */
- ses = Sess_get_session( private_name );
- G_send_self_leave( grp, ses );
- stdskl_erase_key(&grp->mboxes, &Sessions[ses].mbox);
+ /* notify this local member and extract its mbox from group */
+ ses = Sess_get_session( private_name );
+
+ if (ses < 0) {
+ Alarmp( SPLOG_FATAL, GROUPS, "G_handle_leave: member '%s' has no local session in group '%s'\n", private_name, grp->name );
+ }
+
+ G_send_self_leave( grp, ses );
+ G_remove_mailbox( grp, Sessions[ ses ].mbox );
}
/* extract this member from group */
memcpy( departing_private_group_name, mbr->name, MAX_GROUP_NAME );
- stdskl_erase(&dmn->MembersList, &mbr->MembersListIt);
+
+ if (stdskl_is_end(&dmn->MembersList, stdskl_find(&dmn->MembersList, &it, &mbr))) {
+ Alarmp( SPLOG_FATAL, GROUPS, "G_handle_leave: couldn't extract member(%s) from MembersList!\n", mbr->name );
+ }
+
+ stdskl_erase(&dmn->MembersList, &it);
+
dispose(mbr);
grp->num_members--;
- if( dmn->MembersList.size == 0 )
+ if( stdskl_empty(&dmn->MembersList) )
{
G_remove_daemon( grp, dmn );
}
@@ -949,7 +968,7 @@
* We never need to mark a group as changed here, or in G_handle_kill.
*/
- if( !stdskl_empty(&grp->mboxes) )
+ if( !stdarr_empty(&grp->mboxes) )
{
if( grp->changed )
{
@@ -988,7 +1007,7 @@
daemon_members *dmn;
member *mbr;
int ses = -1; /* Fool compiler */
- stdit it;
+ stdit it, tit;
Alarmp( SPLOG_INFO, GROUPS, "G_handle_kill: %s is killed\n", private_group_name );
@@ -1021,11 +1040,11 @@
return;
}
- if( p.id == My.id ) ses = Sess_get_session( private_name );
+ if( p.id == My.id ) ses = Sess_get_session( private_name ); /* FIXME: check for negative answer and error? */
for (stdskl_begin(&GroupsList, &it); !stdskl_is_end(&GroupsList, &it); )
{
- grp = *(group**) stdskl_it_val(&it);
+ grp = *(group**) stdskl_it_key(&it);
stdskl_it_next(&it); /* NOTE: need to do advancement before potential erasure below */
dmn = G_get_daemon( grp, p.id );
@@ -1036,13 +1055,19 @@
/* Extract this member from group */
if( p.id == My.id )
{
- stdskl_erase_key(&grp->mboxes, &Sessions[ses].mbox);
+ G_remove_mailbox( grp, Sessions[ ses ].mbox );
}
memcpy( departing_private_group_name, mbr->name, MAX_GROUP_NAME );
- stdskl_erase(&dmn->MembersList, &mbr->MembersListIt);
+
+ if (stdskl_is_end(&dmn->MembersList, stdskl_find(&dmn->MembersList, &tit, &mbr))) {
+ Alarmp( SPLOG_FATAL, GROUPS, "G_handle_kill: unable to extract member(%s) from MembersList!\n", private_group_name );
+ }
+
+ stdskl_erase_key(&dmn->MembersList, &tit);
+
dispose(mbr);
grp->num_members--;
- if( dmn->MembersList.size == 0 )
+ if( stdskl_empty(&dmn->MembersList) )
{
G_remove_daemon( grp, dmn );
}
@@ -1056,7 +1081,7 @@
/* Increment group id */
grp->grp_id.index++;
- if( !stdskl_empty(&grp->mboxes) )
+ if( !stdarr_empty(&grp->mboxes) )
{
if( grp->changed )
{
@@ -1098,7 +1123,8 @@
char *vs_set_offset_ptr; /* Byte offset into the vs_set region of my vs_set */
char *num_vs_ptr; /* num members in virtual-synchrony/failure-atomicity set */
char *vs_ptr; /* the virtual synchrony set */
- stdit it;
+ mailbox *mbox_ptr;
+ mailbox *endbox_ptr;
msg = Message_new_message();
num_bytes = G_build_memb_buf( grp, msg, Mess_buf, caused );
@@ -1132,9 +1158,14 @@
Obj_Inc_Refcount(mess_link->mess);
needed = 0;
- for (stdskl_begin(&grp->mboxes, &it); !stdskl_is_end(&grp->mboxes, &it); stdskl_it_next(&it))
+
+ mbox_ptr = (mailbox*) grp->mboxes.begin;
+ endbox_ptr = mbox_ptr + grp->mboxes.size;
+
+ for (; mbox_ptr != endbox_ptr; ++mbox_ptr)
{
- ses = Sess_get_session_index ( *(mailbox*) stdskl_it_key(&it) );
+ ses = Sess_get_session_index ( *mbox_ptr );
+
if( Is_memb_session( Sessions[ ses ].status ) )
Sess_write( ses, mess_link, &needed );
}
@@ -1190,7 +1221,8 @@
char *local_vs_set_offset_ptr;
int needed, joiner_needed;
int ses;
- stdit it;
+ mailbox *mbox_ptr;
+ mailbox *endbox_ptr;
msg = Message_new_message();
num_bytes = G_build_memb_vs_buf( grp, msg, Mess_buf, CAUSED_BY_NETWORK, joiner );
@@ -1203,14 +1235,16 @@
/* notify local members */
needed = 0;
- for (stdskl_begin(&grp->mboxes, &it); !stdskl_is_end(&grp->mboxes, &it); stdskl_it_next(&it))
+
+ mbox_ptr = (mailbox*) grp->mboxes.begin;
+ endbox_ptr = mbox_ptr + grp->mboxes.size;
+
+ for (; mbox_ptr != endbox_ptr; ++mbox_ptr)
{
- mailbox m = *(mailbox*) stdskl_it_key(&it);
-
/* if new member is local we do not notify it here. */
- if( joiner != NULL && new_mbox == m) continue;
+ if( joiner != NULL && new_mbox == *mbox_ptr) continue;
- ses = Sess_get_session_index ( m );
+ ses = Sess_get_session_index ( *mbox_ptr );
if( Is_memb_session( Sessions[ ses ].status ) )
Sess_write( ses, mess_link, &needed );
}
@@ -1253,16 +1287,19 @@
message_link *mess_link;
int needed;
int ses;
- stdit it;
+ mailbox *mbox_ptr;
+ mailbox *endbox_ptr;
/* send members transitional membership */
mess_link = G_build_trans_mess( grp );
needed = 0;
- for (stdskl_begin(&grp->mboxes, &it); !stdskl_is_end(&grp->mboxes, &it); stdskl_it_next(&it))
+
+ mbox_ptr = (mailbox*) grp->mboxes.begin;
+ endbox_ptr = mbox_ptr + grp->mboxes.size;
+
+ for (; mbox_ptr != endbox_ptr; ++mbox_ptr)
{
- mailbox m = *(mailbox*) stdskl_it_key(&it);
-
- ses = Sess_get_session_index ( m );
+ ses = Sess_get_session_index ( *mbox_ptr );
if( Is_memb_session( Sessions[ ses ].status ) )
Sess_write( ses, mess_link, &needed );
}
@@ -1453,7 +1490,7 @@
for (stdskl_begin(&GroupsList, &it); !stdskl_is_end(&GroupsList, &it); )
{
- grp = *(group**) stdskl_it_val(&it);
+ grp = *(group**) stdskl_it_key(&it);
stdskl_it_next(&it); /* NOTE: need to do advancement before potential erasure below */
/*
@@ -1481,7 +1518,7 @@
grp->grp_id.memb_id = Reg_memb_id;
grp->grp_id.index = 1;
grp->changed = 0;
- if( !stdskl_empty(&grp->mboxes) )
+ if( !stdarr_empty(&grp->mboxes) )
G_send_heavyweight_memb( grp );
G_update_daemon_memb_ids( grp );
}
@@ -1511,16 +1548,17 @@
stdskl_find(&GroupsList, &it, &group_name);
- return (!stdskl_is_end(&GroupsList, &it) ? *(group**) stdskl_it_val(&it) : NULL);
+ return (!stdskl_is_end(&GroupsList, &it) ? *(group**) stdskl_it_key(&it) : NULL);
}
static daemon_members *G_get_daemon( group *grp, int32u proc_id )
{
- stdit it;
+ stdit it;
+ int32u * proc_id_ptr = &proc_id;
- stdskl_find(&grp->DaemonsList, &it, &proc_id);
+ stdskl_find(&grp->DaemonsList, &it, &proc_id_ptr);
- return (!stdskl_is_end(&grp->DaemonsList, &it) ? *(daemon_members**) stdskl_it_val(&it) : NULL);
+ return (!stdskl_is_end(&grp->DaemonsList, &it) ? *(daemon_members**) stdskl_it_key(&it) : NULL);
}
static member *G_get_member( daemon_members *dmn, char *private_group_name )
@@ -1586,12 +1624,12 @@
num_bytes = 0;
for (stdskl_begin(&grp->DaemonsList, &it); !stdskl_is_end(&grp->DaemonsList, &it); )
{
- dmn = *(daemon_members**) stdskl_it_val(&it);
+ dmn = *(daemon_members**) stdskl_it_key(&it);
stdskl_it_next(&it); /* NOTE: need to do advancement before potential erasure below */
for (stdskl_begin(&dmn->MembersList, &mit); !stdskl_is_end(&dmn->MembersList, &mit); )
{
- mbr = *(member**) stdskl_it_val(&mit);
+ mbr = *(member**) stdskl_it_key(&mit);
stdskl_it_next(&mit); /* NOTE: need to do advancement before potential erasure below */
memb_ptr = &buf[num_bytes];
@@ -1682,16 +1720,14 @@
/* Points to the front of the vs_sets */
vs_set_region_ptr = &buf[num_bytes];
- /* Basically, use the skiplist to do an insertion sort. */
+ /* use a skiplist to sort all of the group's daemons by memb_id (primary) and then by proc_id (secondary) */
+
if (stdskl_construct(&temp, sizeof(daemon_members*), 0, G_compare_daemon_vs_set) != 0) {
Alarmp( SPLOG_FATAL, GROUPS, "%s: %d: memory allocation failed\n", __FILE__, __LINE__ );
}
- for (stdskl_begin(&grp->DaemonsList, &it); !stdskl_is_end(&grp->DaemonsList, &it); stdskl_it_next(&it))
- {
- if (stdskl_insert(&temp, NULL, (daemon_members**) stdskl_it_val(&it), NULL, STDFALSE) != 0) {
- Alarmp( SPLOG_FATAL, GROUPS, "%s: %d: memory allocation failed\n", __FILE__, __LINE__ );
- }
+ if (stdskl_put_seq_n(&temp, NULL, stdskl_begin(&grp->DaemonsList, &it), stdskl_size(&grp->DaemonsList), STDFALSE) != 0) {
+ Alarmp( SPLOG_FATAL, GROUPS, "%s: %d: memory allocation failed\n", __FILE__, __LINE__ );
}
curr_vs_set_memb_id = unknown_memb_id;
@@ -1727,12 +1763,13 @@
/* Handle changed-group join during transitional. The joiner does not
* get to be listed with everyone else from his daemon, but rather at
* the end, in a self vs set. */
- if( joiner != NULL && !found_joiner )
+ if( joiner != NULL && !found_joiner ) {
if( strcmp( joiner->name, mbr->name ) == 0 )
{
found_joiner = 1;
continue;
}
+ }
membs_ptr = &buf[num_bytes];
num_bytes += MAX_GROUP_NAME;
head_ptr->data_len += MAX_GROUP_NAME;
@@ -1865,7 +1902,7 @@
couldnt_fit_daemon = 0;
while (!stdskl_is_end(&GroupsList, git))
{
- grp = *(group**) stdskl_it_val(git);
+ grp = *(group**) stdskl_it_key(git);
if (first_time) { /* initialize dit on first call to this fcn */
stdskl_begin(&grp->DaemonsList, dit);
@@ -1888,12 +1925,12 @@
for (; !stdskl_is_end(&grp->DaemonsList, dit); stdskl_it_next(dit))
{
- dmn = *(daemon_members**) stdskl_it_val(dit);
+ dmn = *(daemon_members**) stdskl_it_key(dit);
/* To store this daemon's information about the current group,
* we need to be able to store its proc_id, memb_id, number of
* local members, and the private group names of its local members. */
size_needed = sizeof(int32) + sizeof(membership_id) + sizeof(int16u) +
- (dmn->MembersList.size * MAX_GROUP_NAME) + Message_get_data_header_size();
+ (stdskl_size(&dmn->MembersList) * MAX_GROUP_NAME) + Message_get_data_header_size();
/* This requires that the number of local group members be limited. */
if( size_needed > GROUPS_BUF_SIZE - num_bytes )
{
@@ -1923,9 +1960,9 @@
}
memcpy( num_memb_ptr, &num_memb, sizeof(int16u) );
- if( num_memb != dmn->MembersList.size )
+ if( num_memb != stdskl_size(&dmn->MembersList) )
Alarmp( SPLOG_FATAL, GROUPS, "G_build_groups_buf: group %s has %d %d members\n",
- grp->name, num_memb, dmn->MembersList.size );
+ grp->name, num_memb, stdskl_size(&dmn->MembersList) );
num_dmns++;
}
memcpy( num_dmns_ptr, &num_dmns, sizeof(int16u) );
@@ -1935,7 +1972,7 @@
stdskl_it_next(git); /* advance group iterator */
if (!stdskl_is_end(&GroupsList, git)) { /* if loop not done, then init dit iterator for the advanced git */
- grp = *(group**) stdskl_it_val(git);
+ grp = *(group**) stdskl_it_key(git);
stdskl_begin(&grp->DaemonsList, dit);
}
}
@@ -2087,11 +2124,11 @@
memset( grp->name, 0, MAX_GROUP_NAME );
strcpy( grp->name, group_name_ptr );
- if (stdskl_construct(&grp->DaemonsList, sizeof(int32), sizeof(daemon_members*), G_compare_proc_ids_by_conf) != 0) {
+ if (stdskl_construct(&grp->DaemonsList, sizeof(daemon_members*), 0, G_compare_proc_ids_by_conf) != 0) {
Alarmp( SPLOG_FATAL, GROUPS, "%s: %d: memory allocation failed\n", __FILE__, __LINE__ );
}
- if (stdskl_construct(&grp->mboxes, sizeof(mailbox), 0, NULL) != 0) {
+ if (stdarr_construct(&grp->mboxes, sizeof(mailbox), 0) != 0) {
Alarmp( SPLOG_FATAL, GROUPS, "%s: %d: memory allocation failed\n", __FILE__, __LINE__ );
}
@@ -2109,7 +2146,7 @@
grp->grp_id.index = Flip_int32( grp->grp_id.index );
}
- if (stdskl_insert(&GroupsList, &grp->GroupsListIt, &grp->name, &grp, STDFALSE) != 0) {
+ if (stdskl_put(&GroupsList, NULL, &grp, NULL, STDFALSE) != 0) {
Alarmp( SPLOG_FATAL, GROUPS, "%s: %d: memory allocation failed\n", __FILE__, __LINE__ );
}
@@ -2156,7 +2193,7 @@
Alarmp( SPLOG_FATAL, GROUPS, "%s: %d: memory allocation failed\n", __FILE__, __LINE__ );
}
- if (stdskl_insert(&grp->DaemonsList, &dmn->DaemonsListIt, &dmn->proc_id, &dmn, STDFALSE) != 0) {
+ if (stdskl_put(&grp->DaemonsList, NULL, &dmn, NULL, STDFALSE) != 0) {
Alarmp( SPLOG_FATAL, GROUPS, "%s: %d: memory allocation failed\n", __FILE__, __LINE__ );
}
@@ -2164,17 +2201,17 @@
!Memb_is_equal( dmn->memb_id, grp->grp_id.memb_id ) )
grp->changed = 1;
- stdskl_end(&dmn->MembersList, &it);
-
/* creating members */
- for( j = 0, stdskl_end(&dmn->MembersList, &it); j < num_memb; ++j, stdskl_it_next(&it))
+ for( j = 0; j < num_memb; ++j )
{
mbr = new( MEMBER );
memcpy( mbr->name, &Temp_buf[num_bytes], MAX_GROUP_NAME );
Alarmp( SPLOG_DEBUG, GROUPS, "G_mess_to_groups: \t\t%s\n", mbr->name );
num_bytes += MAX_GROUP_NAME;
- if (stdskl_insert(&dmn->MembersList, &it, &mbr, NULL, STDTRUE) != 0) { /* NOTE: hint insert at end */
+ /* this inserts into MembersList hinting that the insertion should be at the end of the list (faster if input sorted) */
+
+ if (stdskl_put(&dmn->MembersList, stdskl_end(&dmn->MembersList, &it), &mbr, NULL, STDTRUE) != 0) {
Alarmp( SPLOG_FATAL, GROUPS, "%s: %d: memory allocation failed\n", __FILE__, __LINE__ );
}
}
@@ -2184,71 +2221,110 @@
return( 0 );
}
+/* TODO: G_analize_groups is O(n) when num_groups = 1 and O(n^2) when
+ num_groups > 1 (multi_group_multicast) in the number of targeted
+ mailboxes. In the latter case, if n is large a O(n lg n) solution
+ leveraging a skiplist would be preferable.
+*/
+
int G_analize_groups( int num_groups, char target_groups[][MAX_GROUP_NAME], int target_sessions[] )
{
+static mailbox mboxes[MAX_SESSIONS];
int num_mbox;
+ mailbox *bigbox_ptr;
+ mailbox *bigend_ptr;
+ mailbox *litbox_ptr;
+ mailbox *litend_ptr;
group *grp;
char proc_name[MAX_PROC_NAME];
char private_name[MAX_PRIVATE_NAME+1];
int ses;
int ret;
int i;
- stdskl mboxes;
- stdit it;
- if (stdskl_construct(&mboxes, sizeof(mailbox), 0, NULL) != 0) {
- Alarmp( SPLOG_FATAL, GROUPS, "%s: %d: memory allocation failed\n", __FILE__, __LINE__ );
- }
+ /* collect the target local mailboxen */
- /* get the mbox */
- num_mbox = 0;
- for( i=0; i < num_groups; i++ )
+ num_mbox = 0;
+ litbox_ptr = NULL;
+ litend_ptr = NULL;
+
+ for ( i=0; i < num_groups; ++i )
{
- if( target_groups[i][0] == '#' )
+ if( target_groups[i][0] != '#' )
{
+ /* regular group */
+ grp = G_get_group( target_groups[i] );
+
+ if( grp == NULL ) {
+ continue;
+ }
+
+ if( Gstate == GOP || Gstate == GTRANS ) {
+ litbox_ptr = (mailbox*) grp->mboxes.begin; /* point litbox pointer at grp->mboxes */
+ litend_ptr = litbox_ptr + grp->mboxes.size;
+
+ } else {
+ Alarmp( SPLOG_FATAL, GROUPS, "G_analize_groups: Gstate is %d\n", Gstate );
+ }
+
+ } else {
/* private group */
ret = G_private_to_names( target_groups[i], private_name, proc_name );
- /* Illegal group */
- if( ret < 0 ) continue;
+ /* Illegal group OR this private group is not local OR we have no such session */
+ if( ret < 0 || strcmp( My.name, proc_name ) != 0 || (ses = Sess_get_session( private_name )) < 0) {
+ continue;
+ }
- /* this private group is not local */
- if( strcmp( My.name, proc_name ) != 0 ) continue;
+ litbox_ptr = &Sessions[ ses ].mbox; /* just point litbox pointer at the session's mbox */
+ litend_ptr = litbox_ptr + 1;
+ }
- ses = Sess_get_session( private_name );
+ /* NOTE: this code assumes that grp->mboxes contains no duplicates */
- /* we have no such session */
- if( ses < 0 ) continue;
+ if (num_groups == 1) { /* no need to do extra copy work if only one group -> just use litbox 'array' directly */
+ break;
+ }
- if (stdskl_put(&mboxes, NULL, &Sessions[ ses ].mbox, NULL, STDFALSE) != 0) {
- Alarmp( SPLOG_FATAL, GROUPS, "%s: %d: memory allocation failed\n", __FILE__, __LINE__ );
+ if (num_mbox != 0) {
+ bigend_ptr = mboxes + num_mbox;
+
+ for (; litbox_ptr != litend_ptr; ++litbox_ptr)
+ {
+ mailbox m = *litbox_ptr;
+
+ /* linear search over mboxes for 'm' */
+
+ for (bigbox_ptr = mboxes; bigbox_ptr != bigend_ptr && *bigbox_ptr != m; ++bigbox_ptr);
+
+ if (bigbox_ptr == bigend_ptr) {
+ mboxes[ num_mbox++ ] = m;
+ }
}
} else {
- /* regular group */
- grp = G_get_group( target_groups[i] );
- if( grp == NULL ) continue;
- if( Gstate == GOP || Gstate == GTRANS ) {
+ num_mbox = (int) (litend_ptr - litbox_ptr); /* if num_mbox is (still) zero, then adopt litbox 'array' */
+ memcpy(mboxes, litbox_ptr, num_mbox * sizeof(mailbox));
+ }
+ }
- if (stdskl_put_seq_n(&mboxes, NULL, stdskl_begin(&grp->mboxes, &it), stdskl_size(&grp->mboxes), STDFALSE) != 0) {
- Alarmp( SPLOG_FATAL, GROUPS, "%s: %d: memory allocation failed\n", __FILE__, __LINE__ );
- }
+ /* convert mailboxes to sessions */
- } else {
- Alarmp( SPLOG_FATAL, GROUPS, "G_analize_groups: Gstate is %d\n", Gstate );
- }
- }
+ if (num_groups == 1) { /* on non-multi group multicast just use litbox 'array' in place */
+ bigbox_ptr = litbox_ptr;
+ bigend_ptr = litend_ptr;
+
+ } else {
+ bigbox_ptr = mboxes;
+ bigend_ptr = mboxes + num_mbox;
}
-
- /* convert mbox to sessions */
- for (i = 0, stdskl_begin(&mboxes, &it); !stdskl_is_end(&mboxes, &it); ++i, stdskl_it_next(&it))
+
+ for (; bigbox_ptr != bigend_ptr; ++bigbox_ptr, ++target_sessions)
{
- target_sessions[i] = Sess_get_session_index( *(mailbox*) stdskl_it_key(&it) );
+ *target_sessions = Sess_get_session_index( *bigbox_ptr );
}
- stdskl_destruct(&mboxes); /* TODO: old code of array searching probably faster at least for small groups/memberships */
-
- return i;
+ return (int) (bigend_ptr - bigbox_ptr);
}
static void G_compute_group_mask( group *grp, char *func_name )
@@ -2266,8 +2342,11 @@
}
for (stdskl_begin(&grp->DaemonsList, &it); !stdskl_is_end(&grp->DaemonsList, &it); stdskl_it_next(&it))
{
- dmn = *(daemon_members**) stdskl_it_val(&it);
+ dmn = *(daemon_members**) stdskl_it_key(&it);
Conf_proc_by_id( dmn->proc_id, &p );
+
+ /* FIXME: TODO: isn't the following loop the same as: temp = (0x1 << (p.seg_index & 0x1F)); ??? */
+
temp = 1;
for( i = 0; i < p.seg_index%32; i++ )
{
@@ -2417,12 +2496,12 @@
for (i = 0, stdskl_begin(&GroupsList, &git); !stdskl_is_end(&GroupsList, &git); ++i, stdskl_it_next(&git))
{
- grp = *(group**) stdskl_it_val(&git);
+ grp = *(group**) stdskl_it_key(&git);
Alarmp( SPLOG_PRINT, GROUPS, "[%d] group %s with %d members:\n", i+1, grp->name, grp->num_members );
for (j = 0, stdskl_begin(&grp->DaemonsList, &dit); !stdskl_is_end(&grp->DaemonsList, &dit); ++j, stdskl_it_next(&dit))
{
- dmn = *(daemon_members**) stdskl_it_val(&dit);
+ dmn = *(daemon_members**) stdskl_it_key(&dit);
for (k = 0, stdskl_begin(&dmn->MembersList, &mit); !stdskl_is_end(&dmn->MembersList, &mit); ++k, stdskl_it_next(&mit))
{
@@ -2438,7 +2517,7 @@
{
group *grp = G_get_group( group_name );
if( grp == NULL ) return 0;
- return stdskl_size(&grp->mboxes);
+ return stdarr_size(&grp->mboxes);
}
/* Add new members to my synced set. */
@@ -2513,7 +2592,7 @@
for (stdskl_begin(&grp->DaemonsList, &it); !stdskl_is_end(&grp->DaemonsList, &it); )
{
- dmn = *(daemon_members**) stdskl_it_val(&it);
+ dmn = *(daemon_members**) stdskl_it_key(&it);
stdskl_it_next(&it); /* NOTE: advance here to protect against potential removal below */
needed = 0;
@@ -2554,7 +2633,7 @@
for (stdskl_begin(&grp->DaemonsList, &it); !stdskl_is_end(&grp->DaemonsList, &it); stdskl_it_next(&it))
{
- dmn = *(daemon_members**) stdskl_it_val(&it);
+ dmn = *(daemon_members**) stdskl_it_key(&it);
if( Conf_id_in_conf( &Trans_memb, dmn->proc_id ) == -1 )
{
group_changed = 1;
@@ -2566,31 +2645,65 @@
static void G_remove_daemon( group *grp, daemon_members *dmn )
{
- stdit it;
+ stdit it;
+ int32 * proc_id_ptr = &dmn->proc_id;
+
+ if (stdskl_is_end(&grp->DaemonsList, stdskl_find(&grp->DaemonsList, &it, &proc_id_ptr))) {
+ Alarmp( SPLOG_FATAL, GROUPS, "G_remove_daemon: invalid daemon(%d.%d.%d.%d) removal from group(%s)\n",
+ IP1(dmn->proc_id), IP2(dmn->proc_id), IP3(dmn->proc_id), IP4(dmn->proc_id), grp->name );
+ }
+ stdskl_erase(&grp->DaemonsList, &it);
+
grp->num_members -= stdskl_size(&dmn->MembersList);
for (stdskl_begin(&dmn->MembersList, &it); !stdskl_is_end(&dmn->MembersList, &it); stdskl_it_next(&it)) {
- dispose(*(member**) stdskl_it_val(&it)); /* NOTE: this is only safe because we do destruct immediately after */
+ dispose(*(member**) stdskl_it_key(&it)); /* NOTE: this is only safe because we do destruct immediately after */
}
stdskl_destruct(&dmn->MembersList);
- stdskl_erase(&grp->DaemonsList, &dmn->DaemonsListIt);
dispose(dmn);
}
/* Remove a group that is known to be empty. */
static void G_remove_group( group *grp )
{
+ stdit it;
+
assert( stdskl_empty(&grp->DaemonsList) );
+ assert( stdarr_empty(&grp->mboxes) );
+
+ if (stdskl_is_end(&GroupsList, stdskl_find(&GroupsList, &it, &grp))) {
+ Alarmp( SPLOG_FATAL, GROUPS, "G_remove_group: invalid group removal(%s)\n", grp->name );
+ }
+
+ stdskl_erase(&GroupsList, &it);
+
stdskl_destruct(&grp->DaemonsList);
- stdskl_destruct(&grp->mboxes);
- stdskl_erase(&GroupsList, &grp->GroupsListIt);
+ stdarr_destruct(&grp->mboxes);
dispose(grp);
Num_groups--;
GlobalStatus.num_groups = Num_groups;
}
+/* Remove a local mailbox from grp->mboxes */
+static void G_remove_mailbox( group *grp, mailbox m )
+{
+ mailbox *mbox_ptr = (mailbox*) grp->mboxes.begin; /* address of first entry */
+ mailbox *endbox_ptr = mbox_ptr + grp->mboxes.size; /* address of 1 past last entry */
+
+ for (; mbox_ptr != endbox_ptr && *mbox_ptr != m; ++mbox_ptr); /* linear search over grp->mboxes */
+
+ if (mbox_ptr == endbox_ptr) {
+ Alarmp( SPLOG_FATAL, GROUPS, "G_remove_mailbox: didn't find local mailbox %d in group '%s'\n", m, grp->name );
+ }
+
+ --endbox_ptr; /* point at last entry in grp->mboxes */
+ *mbox_ptr = *endbox_ptr; /* overwrite 'm' entry w/ last entry */
+
+ stdarr_pop_back(&grp->mboxes); /* pop off redundant last entry */
+}
+
/* All non-partitioned daemons get the membership ID component of the
* groups current group ID. */
static void G_update_daemon_memb_ids( group *grp )
@@ -2599,7 +2712,7 @@
for (stdskl_begin(&grp->DaemonsList, &it); !stdskl_is_end(&grp->DaemonsList, &it); stdskl_it_next(&it))
{
- daemon_members *dmn = *(daemon_members**) stdskl_it_val(&it);
+ daemon_members *dmn = *(daemon_members**) stdskl_it_key(&it);
if( Is_established_daemon( dmn ) ) {
dmn->memb_id = grp->grp_id.memb_id;
Modified: trunk/daemon/sess_body.h
===================================================================
--- trunk/daemon/sess_body.h 2005-07-22 08:40:34 UTC (rev 251)
+++ trunk/daemon/sess_body.h 2005-07-28 14:50:56 UTC (rev 252)
@@ -72,26 +72,23 @@
/* All the information we need to maintain per group member is its private
* group name. */
typedef struct dummy_member {
- char name[MAX_GROUP_NAME];
- stdit MembersListIt;
+ char name[MAX_GROUP_NAME]; /* NOTE: groups.c depends on 'name' being first member (MembersList) */
} member;
typedef struct dummy_daemon_members {
- int32 proc_id;
- membership_id memb_id; /* Used for vs_set sorting; unknown_memb_id means partitioned. */
- stdskl MembersList; /* (member*) -> nil */
- stdit DaemonsListIt;
+ int32 proc_id; /* NOTE: groups.c depends on 'proc_id' being the first member (DaemonsList) */
+ membership_id memb_id; /* used for vs_set sorting in G_build_memb_vs_buf; unknown_memb_id means partitioned. */
+ stdskl MembersList; /* (member*) -> nil */
} daemon_members;
typedef struct dummy_group {
- char name[MAX_GROUP_NAME];
+ char name[MAX_GROUP_NAME]; /* NOTE: groups.c depends on 'name' being the first member (GroupsList) */
group_id grp_id;
int changed;
- int num_members; /* sums over all daemons in DaemonsList */
- stdskl DaemonsList; /* (int32) -> (daemon_members*) */
- stdskl mboxes; /* (mailbox) -> nil: mailboxes of local clients */
+ int num_members; /* sums over all daemons in DaemonsList */
+ stdskl DaemonsList; /* (daemon_members*) -> nil */
+ stdarr mboxes; /* (mailbox): local clients unordered */
route_mask grp_mask;
- stdit GroupsListIt;
} group;
#undef ext