aboutsummaryrefslogtreecommitdiffstats
path: root/erts/emulator/beam/erl_monitors.c
diff options
context:
space:
mode:
authorErlang/OTP <[email protected]>2009-11-20 14:54:40 +0000
committerErlang/OTP <[email protected]>2009-11-20 14:54:40 +0000
commit84adefa331c4159d432d22840663c38f155cd4c1 (patch)
treebff9a9c66adda4df2106dfd0e5c053ab182a12bd /erts/emulator/beam/erl_monitors.c
downloadotp-84adefa331c4159d432d22840663c38f155cd4c1.tar.gz
otp-84adefa331c4159d432d22840663c38f155cd4c1.tar.bz2
otp-84adefa331c4159d432d22840663c38f155cd4c1.zip
The R13B03 release.OTP_R13B03
Diffstat (limited to 'erts/emulator/beam/erl_monitors.c')
-rw-r--r--erts/emulator/beam/erl_monitors.c1019
1 files changed, 1019 insertions, 0 deletions
diff --git a/erts/emulator/beam/erl_monitors.c b/erts/emulator/beam/erl_monitors.c
new file mode 100644
index 0000000000..d873c7a701
--- /dev/null
+++ b/erts/emulator/beam/erl_monitors.c
@@ -0,0 +1,1019 @@
+/*
+ * %CopyrightBegin%
+ *
+ * Copyright Ericsson AB 2004-2009. All Rights Reserved.
+ *
+ * The contents of this file are subject to the Erlang Public License,
+ * Version 1.1, (the "License"); you may not use this file except in
+ * compliance with the License. You should have received a copy of the
+ * Erlang Public License along with this software. If not, it can be
+ * retrieved online at http://www.erlang.org/.
+ *
+ * Software distributed under the License is distributed on an "AS IS"
+ * basis, WITHOUT WARRANTY OF ANY KIND, either express or implied. See
+ * the License for the specific language governing rights and limitations
+ * under the License.
+ *
+ * %CopyrightEnd%
+ */
+
+/**************************************************************************
+ * Monitors and links data structure manipulation.
+ * Monitors and links are organized as AVL trees with the reference as
+ * key in the monitor case and the pid of the linked process as key in the
+ * link case. Lookups the order of the references is somewhat special. Local
+ * references are strictly smaller than remote references and are sorted
+ * by inlined comparision functionality. Remote references are handled by the
+ * usual cmp function.
+ * Each Monitor is tagged with different tags depending on which end of the
+ * monitor it is.
+ * A monitor is removed either explicitly by reference or all monitors are
+ * removed when the process exits. No need to access the monitor by pid.
+ **************************************************************************/
+
+#ifdef HAVE_CONFIG_H
+# include "config.h"
+#endif
+
+#include "sys.h"
+#include "erl_vm.h"
+#include "global.h"
+#include "erl_process.h"
+#include "error.h"
+#include "erl_db.h"
+#include "bif.h"
+#include "big.h"
+#include "erl_monitors.h"
+
+#define STACK_NEED 50
+#define MAX_MONITORS 0xFFFFFFFFUL
+
+#define DIR_LEFT 0
+#define DIR_RIGHT 1
+#define DIR_END 2
+
+static erts_smp_atomic_t tot_link_lh_size;
+
+/* Implements the sort order in monitor trees, which is different from
+ the ordinary term order.
+ No short local ref's should ever exist (the ref is created by the bif's
+ in runtime), therefore:
+ All local ref's are less than external ref's
+ Local ref's are inline-compared,
+ External ref's are compared by cmp */
+
+#if 0
+#define CMP_MON_REF(Ref1,Ref2) \
+cmp((Ref1),(Ref2)) /* XXX, the inline comparision yet to be done */
+#else
+#define CMP_MON_REF(Ref1,Ref2) cmp_mon_ref((Ref1),(Ref2))
+#endif
+
+static ERTS_INLINE int cmp_mon_ref(Eterm ref1, Eterm ref2)
+{
+ Eterm *b1, *b2;
+
+
+ b1 = boxed_val(ref1);
+ b2 = boxed_val(ref2);
+ if (is_ref_thing_header(*b1)) {
+ if (is_ref_thing_header(*b2)) {
+ return memcmp(b1+1,b2+1,ERTS_REF_WORDS*sizeof(Uint));
+ }
+ return -1;
+ }
+ if (is_ref_thing_header(*b2)) {
+ return 1;
+ }
+ return cmp(ref1,ref2);
+}
+
+#define CP_LINK_VAL(To, Hp, From) \
+do { \
+ if (IS_CONST(From)) \
+ (To) = (From); \
+ else { \
+ Uint i__; \
+ Uint len__; \
+ ASSERT((Hp)); \
+ ASSERT(is_internal_ref((From)) || is_external((From))); \
+ (To) = make_boxed((Hp)); \
+ len__ = thing_arityval(*boxed_val((From))) + 1; \
+ for(i__ = 0; i__ < len__; i__++) \
+ (*((Hp)++)) = boxed_val((From))[i__]; \
+ if (is_external((To))) { \
+ external_thing_ptr((To))->next = NULL; \
+ erts_refc_inc(&(external_thing_ptr((To))->node->refc), 2);\
+ } \
+ } \
+} while (0)
+
+static ErtsMonitor *create_monitor(Uint type, Eterm ref, Eterm pid, Eterm name)
+{
+ Uint mon_size = ERTS_MONITOR_SIZE;
+ ErtsMonitor *n;
+ Eterm *hp;
+
+ mon_size += NC_HEAP_SIZE(ref);
+ if (!IS_CONST(pid)) {
+ mon_size += NC_HEAP_SIZE(pid);
+ }
+
+ if (mon_size <= ERTS_MONITOR_SH_SIZE) {
+ n = (ErtsMonitor *) erts_alloc(ERTS_ALC_T_MONITOR_SH,
+ mon_size*sizeof(Uint));
+ } else {
+ n = (ErtsMonitor *) erts_alloc(ERTS_ALC_T_MONITOR_LH,
+ mon_size*sizeof(Uint));
+ erts_smp_atomic_add(&tot_link_lh_size, mon_size*sizeof(Uint));
+ }
+ hp = n->heap;
+
+
+ n->left = n->right = NULL; /* Always the same initial value*/
+ n->type = (Uint16) type;
+ n->balance = 0; /* Always the same initial value */
+ n->name = name; /* atom() or [] */
+ CP_LINK_VAL(n->ref, hp, ref); /*XXX Unneccesary check, never immediate*/
+ CP_LINK_VAL(n->pid, hp, pid);
+
+ return n;
+}
+
+static ErtsLink *create_link(Uint type, Eterm pid)
+{
+ Uint lnk_size = ERTS_LINK_SIZE;
+ ErtsLink *n;
+ Eterm *hp;
+
+ if (!IS_CONST(pid)) {
+ lnk_size += NC_HEAP_SIZE(pid);
+ }
+
+ if (lnk_size <= ERTS_LINK_SH_SIZE) {
+ n = (ErtsLink *) erts_alloc(ERTS_ALC_T_NLINK_SH,
+ lnk_size*sizeof(Uint));
+ } else {
+ n = (ErtsLink *) erts_alloc(ERTS_ALC_T_NLINK_LH,
+ lnk_size*sizeof(Uint));
+ erts_smp_atomic_add(&tot_link_lh_size, lnk_size*sizeof(Uint));
+ }
+ hp = n->heap;
+
+
+ n->left = n->right = NULL; /* Always the same initial value*/
+ n->type = (Uint16) type;
+ n->balance = 0; /* Always the same initial value */
+ if (n->type == LINK_NODE) {
+ ERTS_LINK_REFC(n) = 0;
+ } else {
+ ERTS_LINK_ROOT(n) = NULL;
+ }
+ CP_LINK_VAL(n->pid, hp, pid);
+
+ return n;
+}
+
+#undef CP_LINK_VAL
+
+static ErtsSuspendMonitor *create_suspend_monitor(Eterm pid)
+{
+ ErtsSuspendMonitor *smon = erts_alloc(ERTS_ALC_T_SUSPEND_MON,
+ sizeof(ErtsSuspendMonitor));
+ smon->left = smon->right = NULL; /* Always the same initial value */
+ smon->balance = 0; /* Always the same initial value */
+ smon->pending = 0;
+ smon->active = 0;
+ smon->pid = pid;
+ return smon;
+}
+
+void
+erts_init_monitors(void)
+{
+ erts_smp_atomic_init(&tot_link_lh_size, 0);
+}
+
+Uint
+erts_tot_link_lh_size(void)
+{
+ return (Uint) erts_smp_atomic_read(&tot_link_lh_size);
+}
+
+void erts_destroy_monitor(ErtsMonitor *mon)
+{
+ Uint mon_size = ERTS_MONITOR_SIZE;
+ ErlNode *node;
+
+ ASSERT(!IS_CONST(mon->ref));
+ mon_size += NC_HEAP_SIZE(mon->ref);
+ if (is_external(mon->ref)) {
+ node = external_thing_ptr(mon->ref)->node;
+ erts_deref_node_entry(node);
+ }
+ if (!IS_CONST(mon->pid)) {
+ mon_size += NC_HEAP_SIZE(mon->pid);
+ if (is_external(mon->pid)) {
+ node = external_thing_ptr(mon->pid)->node;
+ erts_deref_node_entry(node);
+ }
+ }
+ if (mon_size <= ERTS_MONITOR_SH_SIZE) {
+ erts_free(ERTS_ALC_T_MONITOR_SH, (void *) mon);
+ } else {
+ erts_free(ERTS_ALC_T_MONITOR_LH, (void *) mon);
+ erts_smp_atomic_add(&tot_link_lh_size, -1*mon_size*sizeof(Uint));
+ }
+}
+
+void erts_destroy_link(ErtsLink *lnk)
+{
+ Uint lnk_size = ERTS_LINK_SIZE;
+ ErlNode *node;
+
+ ASSERT(lnk->type == LINK_NODE || ERTS_LINK_ROOT(lnk) == NULL);
+
+ if (!IS_CONST(lnk->pid)) {
+ lnk_size += NC_HEAP_SIZE(lnk->pid);
+ if (is_external(lnk->pid)) {
+ node = external_thing_ptr(lnk->pid)->node;
+ erts_deref_node_entry(node);
+ }
+ }
+ if (lnk_size <= ERTS_LINK_SH_SIZE) {
+ erts_free(ERTS_ALC_T_NLINK_SH, (void *) lnk);
+ } else {
+ erts_free(ERTS_ALC_T_NLINK_LH, (void *) lnk);
+ erts_smp_atomic_add(&tot_link_lh_size, -1*lnk_size*sizeof(Uint));
+ }
+}
+
+void erts_destroy_suspend_monitor(ErtsSuspendMonitor *smon)
+{
+ erts_free(ERTS_ALC_T_SUSPEND_MON, smon);
+}
+
+static void insertion_rotation(int dstack[], int dpos,
+ void *tstack[], int tpos,
+ int state) {
+
+ ErtsMonitorOrLink **this;
+ ErtsMonitorOrLink *p1, *p2, *p;
+ int dir;
+
+ while (state && ( dir = dstack[--dpos] ) != DIR_END) {
+ this = tstack[--tpos];
+ p = *this;
+ if (dir == DIR_LEFT) {
+ switch (p->balance) {
+ case 1:
+ p->balance = 0;
+ state = 0;
+ break;
+ case 0:
+ p->balance = -1;
+ break;
+ case -1: /* The icky case */
+ p1 = p->left;
+ if (p1->balance == -1) { /* Single LL rotation */
+ p->left = p1->right;
+ p1->right = p;
+ p->balance = 0;
+ (*this) = p1;
+ } else { /* Double RR rotation */
+ p2 = p1->right;
+ p1->right = p2->left;
+ p2->left = p1;
+ p->left = p2->right;
+ p2->right = p;
+ p->balance = (p2->balance == -1) ? +1 : 0;
+ p1->balance = (p2->balance == 1) ? -1 : 0;
+ (*this) = p2;
+ }
+ (*this)->balance = 0;
+ state = 0;
+ break;
+ }
+ } else { /* dir == DIR_RIGHT */
+ switch (p->balance) {
+ case -1:
+ p->balance = 0;
+ state = 0;
+ break;
+ case 0:
+ p->balance = 1;
+ break;
+ case 1:
+ p1 = p->right;
+ if (p1->balance == 1) { /* Single RR rotation */
+ p->right = p1->left;
+ p1->left = p;
+ p->balance = 0;
+ (*this) = p1;
+ } else { /* Double RL rotation */
+ p2 = p1->left;
+ p1->left = p2->right;
+ p2->right = p1;
+ p->right = p2->left;
+ p2->left = p;
+ p->balance = (p2->balance == 1) ? -1 : 0;
+ p1->balance = (p2->balance == -1) ? 1 : 0;
+ (*this) = p2;
+ }
+ (*this)->balance = 0;
+ state = 0;
+ break;
+ }
+ }
+ }
+}
+
+void erts_add_monitor(ErtsMonitor **root, Uint type, Eterm ref, Eterm pid,
+ Eterm name)
+{
+ void *tstack[STACK_NEED];
+ int tpos = 0;
+ int dstack[STACK_NEED+1];
+ int dpos = 1;
+ int state = 0;
+ ErtsMonitor **this = root;
+ Sint c;
+
+ dstack[0] = DIR_END;
+ for (;;) {
+ if (!*this) { /* Found our place */
+ state = 1;
+ *this = create_monitor(type,ref,pid,name);
+ break;
+ } else if ((c = CMP_MON_REF(ref,(*this)->ref)) < 0) {
+ /* go left */
+ dstack[dpos++] = DIR_LEFT;
+ tstack[tpos++] = this;
+ this = &((*this)->left);
+ } else if (c > 0) { /* go right */
+ dstack[dpos++] = DIR_RIGHT;
+ tstack[tpos++] = this;
+ this = &((*this)->right);
+ } else { /* Equal key is an error for monitors */
+ erl_exit(1,"Insertion of already present monitor!");
+ break;
+ }
+ }
+ insertion_rotation(dstack, dpos, tstack, tpos, state);
+}
+
+
+/* Returns 0 if OK, < 0 if already present */
+int erts_add_link(ErtsLink **root, Uint type, Eterm pid)
+{
+ void *tstack[STACK_NEED];
+ int tpos = 0;
+ int dstack[STACK_NEED+1];
+ int dpos = 1;
+ int state = 0;
+ ErtsLink **this = root;
+ Sint c;
+
+ dstack[0] = DIR_END;
+ for (;;) {
+ if (!*this) { /* Found our place */
+ state = 1;
+ *this = create_link(type,pid);
+ break;
+ } else if ((c = cmp(pid,(*this)->pid)) < 0) {
+ /* go left */
+ dstack[dpos++] = DIR_LEFT;
+ tstack[tpos++] = this;
+ this = &((*this)->left);
+ } else if (c > 0) { /* go right */
+ dstack[dpos++] = DIR_RIGHT;
+ tstack[tpos++] = this;
+ this = &((*this)->right);
+ } else { /* Equal key is an error for monitors */
+ return -1;
+ }
+ }
+ insertion_rotation(dstack, dpos, tstack, tpos, state);
+ return 0;
+}
+
+ErtsSuspendMonitor *
+erts_add_or_lookup_suspend_monitor(ErtsSuspendMonitor **root, Eterm pid)
+{
+ void *tstack[STACK_NEED];
+ int tpos = 0;
+ int dstack[STACK_NEED+1];
+ int dpos = 1;
+ int state = 0;
+ ErtsSuspendMonitor **this = root;
+ ErtsSuspendMonitor *res;
+ Sint c;
+
+ dstack[0] = DIR_END;
+ for (;;) {
+ if (!*this) { /* Found our place */
+ state = 1;
+ res = *this = create_suspend_monitor(pid);
+ break;
+ } else if ((c = cmp(pid,(*this)->pid)) < 0) {
+ /* go left */
+ dstack[dpos++] = DIR_LEFT;
+ tstack[tpos++] = this;
+ this = &((*this)->left);
+ } else if (c > 0) { /* go right */
+ dstack[dpos++] = DIR_RIGHT;
+ tstack[tpos++] = this;
+ this = &((*this)->right);
+ } else { /* Already here... */
+ ASSERT((*this)->pid == pid);
+ return *this;
+ }
+ }
+ insertion_rotation(dstack, dpos, tstack, tpos, state);
+ return res;
+}
+
+
+/* Returns the new or old link structure */
+ErtsLink *erts_add_or_lookup_link(ErtsLink **root, Uint type, Eterm pid)
+{
+ void *tstack[STACK_NEED];
+ int tpos = 0;
+ int dstack[STACK_NEED+1];
+ int dpos = 1;
+ int state = 0;
+ ErtsLink **this = root;
+ Sint c;
+ ErtsLink *ret = NULL;
+
+ dstack[0] = DIR_END;
+ for (;;) {
+ if (!*this) { /* Found our place */
+ state = 1;
+ *this = create_link(type,pid);
+ ret = *this;
+ break;
+ } else if ((c = cmp(pid,(*this)->pid)) < 0) {
+ /* go left */
+ dstack[dpos++] = DIR_LEFT;
+ tstack[tpos++] = this;
+ this = &((*this)->left);
+ } else if (c > 0) { /* go right */
+ dstack[dpos++] = DIR_RIGHT;
+ tstack[tpos++] = this;
+ this = &((*this)->right);
+ } else { /* Equal key is an error for monitors */
+ return *this;
+ }
+ }
+ insertion_rotation(dstack, dpos, tstack, tpos, state);
+ return ret;
+}
+
+
+/*
+ * Deletion helpers
+ */
+static int balance_left(ErtsMonitorOrLink **this)
+{
+ ErtsMonitorOrLink *p, *p1, *p2;
+ int b1, b2, h = 1;
+
+ p = *this;
+ switch (p->balance) {
+ case -1:
+ p->balance = 0;
+ break;
+ case 0:
+ p->balance = 1;
+ h = 0;
+ break;
+ case 1:
+ p1 = p->right;
+ b1 = p1->balance;
+ if (b1 >= 0) { /* Single RR rotation */
+ p->right = p1->left;
+ p1->left = p;
+ if (b1 == 0) {
+ p->balance = 1;
+ p1->balance = -1;
+ h = 0;
+ } else {
+ p->balance = p1->balance = 0;
+ }
+ (*this) = p1;
+ } else { /* Double RL rotation */
+ p2 = p1->left;
+ b2 = p2->balance;
+ p1->left = p2->right;
+ p2->right = p1;
+ p->right = p2->left;
+ p2->left = p;
+ p->balance = (b2 == 1) ? -1 : 0;
+ p1->balance = (b2 == -1) ? 1 : 0;
+ p2->balance = 0;
+ (*this) = p2;
+ }
+ break;
+ }
+ return h;
+}
+
+static int balance_right(ErtsMonitorOrLink **this)
+{
+ ErtsMonitorOrLink *p, *p1, *p2;
+ int b1, b2, h = 1;
+
+ p = *this;
+ switch (p->balance) {
+ case 1:
+ p->balance = 0;
+ break;
+ case 0:
+ p->balance = -1;
+ h = 0;
+ break;
+ case -1:
+ p1 = p->left;
+ b1 = p1->balance;
+ if (b1 <= 0) { /* Single LL rotation */
+ p->left = p1->right;
+ p1->right = p;
+ if (b1 == 0) {
+ p->balance = -1;
+ p1->balance = 1;
+ h = 0;
+ } else {
+ p->balance = p1->balance = 0;
+ }
+ (*this) = p1;
+ } else { /* Double LR rotation */
+ p2 = p1->right;
+ b2 = p2->balance;
+ p1->right = p2->left;
+ p2->left = p1;
+ p->left = p2->right;
+ p2->right = p;
+ p->balance = (b2 == -1) ? 1 : 0;
+ p1->balance = (b2 == 1) ? -1 : 0;
+ p2->balance = 0;
+ (*this) = p2;
+ }
+ }
+ return h;
+}
+
+static int delsub(ErtsMonitorOrLink **this)
+{
+ ErtsMonitorOrLink **tstack[STACK_NEED];
+ int tpos = 0;
+ ErtsMonitorOrLink *q = (*this);
+ ErtsMonitorOrLink **r = &(q->left);
+ int h;
+
+ /*
+ * Walk down the tree to the right and search
+ * for a void right child, pick that child out
+ * and return it to be put in the deleted
+ * object's place.
+ */
+
+ while ((*r)->right != NULL) {
+ tstack[tpos++] = r;
+ r = &((*r)->right);
+ }
+ *this = *r;
+ *r = (*r)->left;
+ (*this)->left = q->left;
+ (*this)->right = q->right;
+ (*this)->balance = q->balance;
+ tstack[0] = &((*this)->left);
+ h = 1;
+ while (tpos && h) {
+ r = tstack[--tpos];
+ h = balance_right(r);
+ }
+ return h;
+}
+
+ErtsMonitor *erts_remove_monitor(ErtsMonitor **root, Eterm ref)
+{
+ ErtsMonitor **tstack[STACK_NEED];
+ int tpos = 0;
+ int dstack[STACK_NEED+1];
+ int dpos = 1;
+ int state = 0;
+ ErtsMonitor **this = root;
+ Sint c;
+ int dir;
+ ErtsMonitor *q = NULL;
+
+ dstack[0] = DIR_END;
+ for (;;) {
+ if (!*this) { /* Failure */
+ return NULL;
+ } else if ((c = CMP_MON_REF(ref,(*this)->ref)) < 0) {
+ dstack[dpos++] = DIR_LEFT;
+ tstack[tpos++] = this;
+ this = &((*this)->left);
+ } else if (c > 0) { /* go right */
+ dstack[dpos++] = DIR_RIGHT;
+ tstack[tpos++] = this;
+ this = &((*this)->right);
+ } else { /* Equal key, found the one to delete */
+ q = (*this);
+ if (q->right == NULL) {
+ (*this) = q->left;
+ state = 1;
+ } else if (q->left == NULL) {
+ (*this) = q->right;
+ state = 1;
+ } else {
+ dstack[dpos++] = DIR_LEFT;
+ tstack[tpos++] = this;
+ state = delsub((ErtsMonitorOrLink **) this);
+ }
+ break;
+ }
+ }
+ while (state && ( dir = dstack[--dpos] ) != DIR_END) {
+ this = tstack[--tpos];
+ if (dir == DIR_LEFT) {
+ state = balance_left((ErtsMonitorOrLink **) this);
+ } else {
+ state = balance_right((ErtsMonitorOrLink **) this);
+ }
+ }
+ return q;
+}
+
+ErtsLink *erts_remove_link(ErtsLink **root, Eterm pid)
+{
+ ErtsLink **tstack[STACK_NEED];
+ int tpos = 0;
+ int dstack[STACK_NEED+1];
+ int dpos = 1;
+ int state = 0;
+ ErtsLink **this = root;
+ Sint c;
+ int dir;
+ ErtsLink *q = NULL;
+
+ dstack[0] = DIR_END;
+ for (;;) {
+ if (!*this) { /* Failure */
+ return NULL;
+ } else if ((c = cmp(pid,(*this)->pid)) < 0) {
+ dstack[dpos++] = DIR_LEFT;
+ tstack[tpos++] = this;
+ this = &((*this)->left);
+ } else if (c > 0) { /* go right */
+ dstack[dpos++] = DIR_RIGHT;
+ tstack[tpos++] = this;
+ this = &((*this)->right);
+ } else { /* Equal key, found the one to delete */
+ q = (*this);
+ if (q->right == NULL) {
+ (*this) = q->left;
+ state = 1;
+ } else if (q->left == NULL) {
+ (*this) = q->right;
+ state = 1;
+ } else {
+ dstack[dpos++] = DIR_LEFT;
+ tstack[tpos++] = this;
+ state = delsub((ErtsMonitorOrLink **) this);
+ }
+ break;
+ }
+ }
+ while (state && ( dir = dstack[--dpos] ) != DIR_END) {
+ this = tstack[--tpos];
+ if (dir == DIR_LEFT) {
+ state = balance_left((ErtsMonitorOrLink **) this);
+ } else {
+ state = balance_right((ErtsMonitorOrLink **) this);
+ }
+ }
+ return q;
+}
+
+void
+erts_delete_suspend_monitor(ErtsSuspendMonitor **root, Eterm pid)
+{
+ ErtsSuspendMonitor **tstack[STACK_NEED];
+ int tpos = 0;
+ int dstack[STACK_NEED+1];
+ int dpos = 1;
+ int state = 0;
+ ErtsSuspendMonitor **this = root;
+ Sint c;
+ int dir;
+ ErtsSuspendMonitor *q = NULL;
+
+ dstack[0] = DIR_END;
+ for (;;) {
+ if (!*this) { /* Nothing found */
+ return;
+ } else if ((c = cmp(pid,(*this)->pid)) < 0) {
+ dstack[dpos++] = DIR_LEFT;
+ tstack[tpos++] = this;
+ this = &((*this)->left);
+ } else if (c > 0) { /* go right */
+ dstack[dpos++] = DIR_RIGHT;
+ tstack[tpos++] = this;
+ this = &((*this)->right);
+ } else { /* Equal key, found the one to delete */
+ q = (*this);
+ ASSERT(q->pid == pid);
+ if (q->right == NULL) {
+ (*this) = q->left;
+ state = 1;
+ } else if (q->left == NULL) {
+ (*this) = q->right;
+ state = 1;
+ } else {
+ dstack[dpos++] = DIR_LEFT;
+ tstack[tpos++] = this;
+ state = delsub((ErtsMonitorOrLink **) this);
+ }
+ erts_destroy_suspend_monitor(q);
+ break;
+ }
+ }
+ while (state && ( dir = dstack[--dpos] ) != DIR_END) {
+ this = tstack[--tpos];
+ if (dir == DIR_LEFT) {
+ state = balance_left((ErtsMonitorOrLink **) this);
+ } else {
+ state = balance_right((ErtsMonitorOrLink **) this);
+ }
+ }
+}
+
+ErtsMonitor *erts_lookup_monitor(ErtsMonitor *root, Eterm ref)
+{
+ Sint c;
+
+ for (;;) {
+ if (root == NULL || (c = CMP_MON_REF(ref,root->ref)) == 0) {
+ return root;
+ } else if (c < 0) {
+ root = root->left;
+ } else { /* c > 0 */
+ root = root->right;
+ }
+ }
+}
+
+ErtsLink *erts_lookup_link(ErtsLink *root, Eterm pid)
+{
+ Sint c;
+
+ for (;;) {
+ if (root == NULL || (c = cmp(pid,root->pid)) == 0) {
+ return root;
+ } else if (c < 0) {
+ root = root->left;
+ } else { /* c > 0 */
+ root = root->right;
+ }
+ }
+}
+
+ErtsSuspendMonitor *
+erts_lookup_suspend_monitor(ErtsSuspendMonitor *root, Eterm pid)
+{
+ Sint c;
+
+ for (;;) {
+ if (root == NULL || (c = cmp(pid,root->pid)) == 0) {
+ return root;
+ } else if (c < 0) {
+ root = root->left;
+ } else { /* c > 0 */
+ root = root->right;
+ }
+ }
+}
+
+void erts_sweep_monitors(ErtsMonitor *root,
+ void (*doit)(ErtsMonitor *, void *),
+ void *context)
+{
+ ErtsMonitor *tstack[STACK_NEED];
+ int tpos = 0;
+ int dstack[STACK_NEED+1];
+ int dpos = 1;
+ int dir;
+
+ dstack[0] = DIR_END;
+
+ for (;;) {
+ if (root == NULL) {
+ if ((dir = dstack[dpos-1]) == DIR_END) {
+ return;
+ }
+ if (dir == DIR_LEFT) {
+ /* Still has DIR_RIGHT to do */
+ dstack[dpos-1] = DIR_RIGHT;
+ root = (tstack[tpos-1])->right;
+ } else {
+ /* stacktop is an object to be deleted */
+ (*doit)(tstack[--tpos],context); /* expeted to do the
+ deletion */
+ --dpos;
+ root = NULL;
+ }
+ } else {
+ dstack[dpos++] = DIR_LEFT;
+ tstack[tpos++] = root;
+ root = root->left;
+ }
+ }
+}
+
+void erts_sweep_links(ErtsLink *root,
+ void (*doit)(ErtsLink *, void *),
+ void *context)
+{
+ ErtsLink *tstack[STACK_NEED];
+ int tpos = 0;
+ int dstack[STACK_NEED+1];
+ int dpos = 1;
+ int dir;
+
+ dstack[0] = DIR_END;
+
+ for (;;) {
+ if (root == NULL) {
+ if ((dir = dstack[dpos-1]) == DIR_END) {
+ return;
+ }
+ if (dir == DIR_LEFT) {
+ /* Still has DIR_RIGHT to do */
+ dstack[dpos-1] = DIR_RIGHT;
+ root = (tstack[tpos-1])->right;
+ } else {
+ /* stacktop is an object to be deleted */
+ (*doit)(tstack[--tpos],context); /* expeted to do the
+ deletion */
+ --dpos;
+ root = NULL;
+ }
+ } else {
+ dstack[dpos++] = DIR_LEFT;
+ tstack[tpos++] = root;
+ root = root->left;
+ }
+ }
+}
+
+void erts_sweep_suspend_monitors(ErtsSuspendMonitor *root,
+ void (*doit)(ErtsSuspendMonitor *, void *),
+ void *context)
+{
+ ErtsSuspendMonitor *tstack[STACK_NEED];
+ int tpos = 0;
+ int dstack[STACK_NEED+1];
+ int dpos = 1;
+ int dir;
+
+ dstack[0] = DIR_END;
+
+ for (;;) {
+ if (root == NULL) {
+ if ((dir = dstack[dpos-1]) == DIR_END) {
+ return;
+ }
+ if (dir == DIR_LEFT) {
+ /* Still has DIR_RIGHT to do */
+ dstack[dpos-1] = DIR_RIGHT;
+ root = (tstack[tpos-1])->right;
+ } else {
+ /* stacktop is an object to be deleted */
+ (*doit)(tstack[--tpos],context); /* expeted to do the
+ deletion */
+ --dpos;
+ root = NULL;
+ }
+ } else {
+ dstack[dpos++] = DIR_LEFT;
+ tstack[tpos++] = root;
+ root = root->left;
+ }
+ }
+}
+
+
+/* Debug BIF, always present, but undocumented... */
+
+static void erts_dump_monitors(ErtsMonitor *root, int indent)
+{
+ if (root == NULL)
+ return;
+ erts_dump_monitors(root->right,indent+2);
+ erts_printf("%*s[%b16d:%b16u:%T:%T:%T]\n", indent, "", root->balance,
+ root->type, root->ref, root->pid, root->name);
+ erts_dump_monitors(root->left,indent+2);
+}
+
+static void erts_dump_links_aux(ErtsLink *root, int indent,
+ erts_dsprintf_buf_t *dsbufp)
+{
+ if (root == NULL)
+ return;
+ erts_dump_links_aux(root->right, indent+2, dsbufp);
+ dsbufp->str_len = 0;
+ erts_dsprintf(dsbufp, "%*s[%b16d:%b16u:%T:%p]", indent, "",
+ root->balance, root->type, root->pid, ERTS_LINK_ROOT(root));
+ if (ERTS_LINK_ROOT(root) != NULL) {
+ ErtsLink *sub = ERTS_LINK_ROOT(root);
+ int len = dsbufp->str_len;
+ erts_dump_links_aux(sub->right, indent+len+5, dsbufp);
+ erts_dsprintf(dsbufp, "-> %*s[%b16d:%b16u:%T:%p]", indent, "",
+ sub->balance, sub->type, sub->pid, ERTS_LINK_ROOT(sub));
+ erts_printf("%s\n", dsbufp->str);
+ erts_dump_links_aux(sub->left, indent+len+5, dsbufp);
+ } else {
+ erts_printf("%s\n", dsbufp->str);
+ }
+ erts_dump_links_aux(root->left, indent+2, dsbufp);
+}
+
+static void erts_dump_links(ErtsLink *root, int indent)
+{
+ erts_dsprintf_buf_t *dsbufp = erts_create_tmp_dsbuf(0);
+ erts_dump_links_aux(root, indent, dsbufp);
+ erts_destroy_tmp_dsbuf(dsbufp);
+}
+
+Eterm erts_debug_dump_monitors_1(Process *p, Eterm pid)
+{
+ Process *rp;
+ DistEntry *dep;
+ rp = erts_pid2proc(p, ERTS_PROC_LOCK_MAIN, pid, ERTS_PROC_LOCK_LINK);
+ if (!rp) {
+ ERTS_SMP_ASSERT_IS_NOT_EXITING(p);
+ if (is_atom(pid) && is_node_name_atom(pid) &&
+ (dep = erts_find_dist_entry(pid)) != NULL) {
+ erts_printf("Dumping dist monitors-------------------\n");
+ erts_smp_de_links_lock(dep);
+ erts_dump_monitors(dep->monitors,0);
+ erts_smp_de_links_unlock(dep);
+ erts_printf("Monitors dumped-------------------------\n");
+ erts_deref_dist_entry(dep);
+ BIF_RET(am_true);
+ } else {
+ BIF_ERROR(p,BADARG);
+ }
+ } else {
+ erts_printf("Dumping pid monitors--------------------\n");
+ erts_dump_monitors(rp->monitors,0);
+ erts_printf("Monitors dumped-------------------------\n");
+ erts_smp_proc_unlock(rp, ERTS_PROC_LOCK_LINK);
+ BIF_RET(am_true);
+ }
+}
+
+Eterm erts_debug_dump_links_1(Process *p, Eterm pid)
+{
+ Process *rp;
+ DistEntry *dep;
+ if (is_internal_port(pid)) {
+ Port *rport = erts_id2port(pid, p, ERTS_PROC_LOCK_MAIN);
+ if (rport) {
+ erts_printf("Dumping port links----------------------\n");
+ erts_dump_links(rport->nlinks,0);
+ erts_printf("Links dumped----------------------------\n");
+ erts_smp_port_unlock(rport);
+ BIF_RET(am_true);
+ } else {
+ BIF_ERROR(p,BADARG);
+ }
+ } else {
+ rp = erts_pid2proc(p, ERTS_PROC_LOCK_MAIN, pid, ERTS_PROC_LOCK_LINK);
+ if (!rp) {
+ ERTS_SMP_ASSERT_IS_NOT_EXITING(p);
+ if (is_atom(pid) && is_node_name_atom(pid) &&
+ (dep = erts_find_dist_entry(pid)) != NULL) {
+ erts_printf("Dumping dist links----------------------\n");
+ erts_smp_de_links_lock(dep);
+ erts_dump_links(dep->nlinks,0);
+ erts_smp_de_links_unlock(dep);
+ erts_printf("Links dumped----------------------------\n");
+ erts_deref_dist_entry(dep);
+ BIF_RET(am_true);
+ } else {
+ BIF_ERROR(p,BADARG);
+ }
+
+ } else {
+ erts_printf("Dumping pid links-----------------------\n");
+ erts_dump_links(rp->nlinks,0);
+ erts_printf("Links dumped----------------------------\n");
+ erts_smp_proc_unlock(rp, ERTS_PROC_LOCK_LINK);
+ BIF_RET(am_true);
+ }
+ }
+}