[mirror_frr.git] / babeld / resend.c

// SPDX-License-Identifier: MIT
/*
Copyright (c) 2007, 2008 by Juliusz Chroboczek
*/

#ifdef HAVE_CONFIG_H
#include "config.h"
#endif

#include <sys/time.h>
#include <time.h>
#include <string.h>
#include <stdlib.h>

#include <zebra.h>
#include "if.h"

#include "babel_main.h"
#include "babeld.h"
#include "util.h"
#include "neighbour.h"
#include "resend.h"
#include "message.h"
#include "babel_interface.h"

struct timeval resend_time = {0, 0};
struct resend *to_resend = NULL;

static int
resend_match(struct resend *resend,
             int kind, const unsigned char *prefix, unsigned char plen)
{
    return (resend->kind == kind &&
            resend->plen == plen && memcmp(resend->prefix, prefix, 16) == 0);
}

/* This is called by neigh.c when a neighbour is flushed */

void
flush_resends(struct neighbour *neigh)
{
    /* Nothing for now */
}

static struct resend *
find_resend(int kind, const unsigned char *prefix, unsigned char plen,
             struct resend **previous_return)
{
    struct resend *current, *previous;

    previous = NULL;
    current = to_resend;
    while(current) {
        if(resend_match(current, kind, prefix, plen)) {
            if(previous_return)
                *previous_return = previous;
            return current;
        }
        previous = current;
        current = current->next;
    }

    return NULL;
}

struct resend *
find_request(const unsigned char *prefix, unsigned char plen,
             struct resend **previous_return)
{
    return find_resend(RESEND_REQUEST, prefix, plen, previous_return);
}

int
record_resend(int kind, const unsigned char *prefix, unsigned char plen,
              unsigned short seqno, const unsigned char *id,
              struct interface *ifp, int delay)
{
    struct resend *resend;
    unsigned int ifindex = ifp ? ifp->ifindex : 0;

    if((kind == RESEND_REQUEST &&
        input_filter(NULL, prefix, plen, NULL, ifindex) >= INFINITY) ||
       (kind == RESEND_UPDATE &&
        output_filter(NULL, prefix, plen, ifindex) >= INFINITY))
        return 0;

    if(delay >= 0xFFFF)
        delay = 0xFFFF;

    resend = find_resend(kind, prefix, plen, NULL);
    if(resend) {
        if(resend->delay && delay)
            resend->delay = MIN(resend->delay, delay);
        else if(delay)
            resend->delay = delay;
        resend->time = babel_now;
        resend->max = RESEND_MAX;
        if(id && memcmp(resend->id, id, 8) == 0 &&
           seqno_compare(resend->seqno, seqno) > 0) {
            return 0;
        }
        if(id)
            memcpy(resend->id, id, 8);
        else
            memset(resend->id, 0, 8);
        resend->seqno = seqno;
        if(resend->ifp != ifp)
            resend->ifp = NULL;
    } else {
        resend = malloc(sizeof(struct resend));
        if(resend == NULL)
            return -1;
        resend->kind = kind;
        resend->max = RESEND_MAX;
        resend->delay = delay;
        memcpy(resend->prefix, prefix, 16);
        resend->plen = plen;
        resend->seqno = seqno;
        if(id)
            memcpy(resend->id, id, 8);
        else
            memset(resend->id, 0, 8);
        resend->ifp = ifp;
        resend->time = babel_now;
        resend->next = to_resend;
        to_resend = resend;
    }

    if(resend->delay) {
        struct timeval timeout;
        timeval_add_msec(&timeout, &resend->time, resend->delay);
        timeval_min(&resend_time, &timeout);
    }
    return 1;
}

static int
resend_expired(struct resend *resend)
{
    switch(resend->kind) {
    case RESEND_REQUEST:
        return timeval_minus_msec(&babel_now, &resend->time) >= REQUEST_TIMEOUT;
    default:
        return resend->max <= 0;
    }
}

int
unsatisfied_request(const unsigned char *prefix, unsigned char plen,
                    unsigned short seqno, const unsigned char *id)
{
    struct resend *request;

    request = find_request(prefix, plen, NULL);
    if(request == NULL || resend_expired(request))
        return 0;

    if(memcmp(request->id, id, 8) != 0 ||
       seqno_compare(request->seqno, seqno) <= 0)
        return 1;

    return 0;
}

/* Determine whether a given request should be forwarded. */
int
request_redundant(struct interface *ifp,
                  const unsigned char *prefix, unsigned char plen,
                  unsigned short seqno, const unsigned char *id)
{
    struct resend *request;

    request = find_request(prefix, plen, NULL);
    if(request == NULL || resend_expired(request))
        return 0;

    if(memcmp(request->id, id, 8) == 0 &&
       seqno_compare(request->seqno, seqno) > 0)
        return 0;

    if(request->ifp != NULL && request->ifp != ifp)
        return 0;

    if(request->max > 0)
        /* Will be resent. */
        return 1;

    if(timeval_minus_msec(&babel_now, &request->time) <
       (ifp ? MIN(babel_get_if_nfo(ifp)->hello_interval, 1000) : 1000))
        /* Fairly recent. */
        return 1;

    return 0;
}

int
satisfy_request(const unsigned char *prefix, unsigned char plen,
                unsigned short seqno, const unsigned char *id,
                struct interface *ifp)
{
    struct resend *request, *previous;

    request = find_request(prefix, plen, &previous);
    if(request == NULL)
        return 0;

    if(ifp != NULL && request->ifp != ifp)
        return 0;

    if(memcmp(request->id, id, 8) != 0 ||
       seqno_compare(request->seqno, seqno) <= 0) {
        /* We cannot remove the request, as we may be walking the list right
           now.  Mark it as expired, so that expire_resend will remove it. */
        request->max = 0;
        request->time.tv_sec = 0;
        recompute_resend_time();
        return 1;
    }

    return 0;
}

void
expire_resend(void)
{
    struct resend *current, *previous;
    int recompute = 0;

    previous = NULL;
    current = to_resend;
    while(current) {
        if(resend_expired(current)) {
            if(previous == NULL) {
                to_resend = current->next;
                free(current);
                current = to_resend;
            } else {
                previous->next = current->next;
                free(current);
                current = previous->next;
            }
            recompute = 1;
        } else {
            previous = current;
            current = current->next;
        }
    }
    if(recompute)
        recompute_resend_time();
}

void
recompute_resend_time(void)
{
    struct resend *request;
    struct timeval resend = {0, 0};

    request = to_resend;
    while(request) {
        if(!resend_expired(request) && request->delay > 0 && request->max > 0) {
            struct timeval timeout;
            timeval_add_msec(&timeout, &request->time, request->delay);
            timeval_min(&resend, &timeout);
        }
        request = request->next;
    }

    resend_time = resend;
}

void
do_resend(void)
{
    struct resend *resend;

    resend = to_resend;
    while(resend) {
        if(!resend_expired(resend) && resend->delay > 0 && resend->max > 0) {
            struct timeval timeout;
            timeval_add_msec(&timeout, &resend->time, resend->delay);
            if(timeval_compare(&babel_now, &timeout) >= 0) {
                switch(resend->kind) {
                case RESEND_REQUEST:
                    send_multihop_request(resend->ifp,
                                          resend->prefix, resend->plen,
                                          resend->seqno, resend->id, 127);
                    break;
                case RESEND_UPDATE:
                    send_update(resend->ifp, 1,
                                resend->prefix, resend->plen);
                    break;
                default: abort();
                }
                resend->delay = MIN(0xFFFF, resend->delay * 2);
                resend->max--;
            }
        }
        resend = resend->next;
    }
    recompute_resend_time();
}
Commit	Line	Data
acddc0ed	1	// SPDX-License-Identifier: MIT
ca10883e DS	2	/*
ca10883e DS	3	Copyright (c) 2007, 2008 by Juliusz Chroboczek
ca10883e DS	4	*/
ca10883e DS	5
b45ac5f5 DL	6	#ifdef HAVE_CONFIG_H
	7	#include "config.h"
	8	#endif
	9
ca10883e DS	10	#include <sys/time.h>
	11	#include <time.h>
	12	#include <string.h>
	13	#include <stdlib.h>
	14
	15	#include <zebra.h>
	16	#include "if.h"
	17
	18	#include "babel_main.h"
	19	#include "babeld.h"
	20	#include "util.h"
	21	#include "neighbour.h"
	22	#include "resend.h"
	23	#include "message.h"
	24	#include "babel_interface.h"
	25
	26	struct timeval resend_time = {0, 0};
	27	struct resend *to_resend = NULL;
	28
	29	static int
	30	resend_match(struct resend *resend,
	31	int kind, const unsigned char *prefix, unsigned char plen)
	32	{
	33	return (resend->kind == kind &&
	34	resend->plen == plen && memcmp(resend->prefix, prefix, 16) == 0);
	35	}
	36
	37	/* This is called by neigh.c when a neighbour is flushed */
	38
	39	void
	40	flush_resends(struct neighbour *neigh)
	41	{
	42	/* Nothing for now */
	43	}
	44
	45	static struct resend *
	46	find_resend(int kind, const unsigned char *prefix, unsigned char plen,
	47	struct resend **previous_return)
	48	{
	49	struct resend current, previous;
	50
	51	previous = NULL;
	52	current = to_resend;
	53	while(current) {
	54	if(resend_match(current, kind, prefix, plen)) {
	55	if(previous_return)
	56	*previous_return = previous;
	57	return current;
	58	}
	59	previous = current;
	60	current = current->next;
	61	}
	62
	63	return NULL;
	64	}
	65
	66	struct resend *
	67	find_request(const unsigned char *prefix, unsigned char plen,
	68	struct resend **previous_return)
	69	{
	70	return find_resend(RESEND_REQUEST, prefix, plen, previous_return);
	71	}
	72
	73	int
74	record_resend(int kind, const unsigned char *prefix, unsigned char plen,
75	unsigned short seqno, const unsigned char *id,
76	struct interface *ifp, int delay)
77	{
78	struct resend *resend;
79	unsigned int ifindex = ifp ? ifp->ifindex : 0;
80
81	if((kind == RESEND_REQUEST &&
82	input_filter(NULL, prefix, plen, NULL, ifindex) >= INFINITY) \|\|
83	(kind == RESEND_UPDATE &&
84	output_filter(NULL, prefix, plen, ifindex) >= INFINITY))
85	return 0;
86
87	if(delay >= 0xFFFF)
88	delay = 0xFFFF;
89
90	resend = find_resend(kind, prefix, plen, NULL);
91	if(resend) {
92	if(resend->delay && delay)
93	resend->delay = MIN(resend->delay, delay);
94	else if(delay)
95	resend->delay = delay;
96	resend->time = babel_now;
97	resend->max = RESEND_MAX;
98	if(id && memcmp(resend->id, id, 8) == 0 &&
99	seqno_compare(resend->seqno, seqno) > 0) {
100	return 0;
101	}
102	if(id)
103	memcpy(resend->id, id, 8);
104	else
105	memset(resend->id, 0, 8);
106	resend->seqno = seqno;
107	if(resend->ifp != ifp)
108	resend->ifp = NULL;
109	} else {
110	resend = malloc(sizeof(struct resend));
111	if(resend == NULL)
112	return -1;
113	resend->kind = kind;
114	resend->max = RESEND_MAX;
115	resend->delay = delay;
116	memcpy(resend->prefix, prefix, 16);
117	resend->plen = plen;
118	resend->seqno = seqno;
119	if(id)
120	memcpy(resend->id, id, 8);
121	else
122	memset(resend->id, 0, 8);
123	resend->ifp = ifp;
124	resend->time = babel_now;
125	resend->next = to_resend;
126	to_resend = resend;
127	}
128
129	if(resend->delay) {
130	struct timeval timeout;
131	timeval_add_msec(&timeout, &resend->time, resend->delay);
132	timeval_min(&resend_time, &timeout);
133	}
134	return 1;
135	}
136
137	static int
138	resend_expired(struct resend *resend)
139	{
140	switch(resend->kind) {
141	case RESEND_REQUEST:
142	return timeval_minus_msec(&babel_now, &resend->time) >= REQUEST_TIMEOUT;
143	default:
144	return resend->max <= 0;
145	}
146	}
147
148	int
149	unsatisfied_request(const unsigned char *prefix, unsigned char plen,
150	unsigned short seqno, const unsigned char *id)
151	{
152	struct resend *request;
153
154	request = find_request(prefix, plen, NULL);
155	if(request == NULL \|\| resend_expired(request))
156	return 0;
157
158	if(memcmp(request->id, id, 8) != 0 \|\|
159	seqno_compare(request->seqno, seqno) <= 0)
160	return 1;
161
162	return 0;
163	}
164
165	/* Determine whether a given request should be forwarded. */
166	int
167	request_redundant(struct interface *ifp,
168	const unsigned char *prefix, unsigned char plen,
169	unsigned short seqno, const unsigned char *id)
170	{
171	struct resend *request;
172
173	request = find_request(prefix, plen, NULL);
174	if(request == NULL \|\| resend_expired(request))
175	return 0;
176
177	if(memcmp(request->id, id, 8) == 0 &&
178	seqno_compare(request->seqno, seqno) > 0)
179	return 0;
180
181	if(request->ifp != NULL && request->ifp != ifp)
182	return 0;
183
184	if(request->max > 0)
185	/* Will be resent. */
186	return 1;
187
188	if(timeval_minus_msec(&babel_now, &request->time) <
189	(ifp ? MIN(babel_get_if_nfo(ifp)->hello_interval, 1000) : 1000))
190	/* Fairly recent. */
191	return 1;
192
193	return 0;
194	}
195
196	int
197	satisfy_request(const unsigned char *prefix, unsigned char plen,
198	unsigned short seqno, const unsigned char *id,
199	struct interface *ifp)
200	{
201	struct resend request, previous;
202
203	request = find_request(prefix, plen, &previous);
204	if(request == NULL)
205	return 0;
206
207	if(ifp != NULL && request->ifp != ifp)
208	return 0;
209
210	if(memcmp(request->id, id, 8) != 0 \|\|
211	seqno_compare(request->seqno, seqno) <= 0) {
212	/* We cannot remove the request, as we may be walking the list right
213	now. Mark it as expired, so that expire_resend will remove it. */
214	request->max = 0;
215	request->time.tv_sec = 0;
216	recompute_resend_time();
217	return 1;
218	}
219
220	return 0;
221	}
222
223	void
4d762f26	224	expire_resend(void)
ca10883e DS	225	{
	226	struct resend current, previous;
	227	int recompute = 0;
	228
	229	previous = NULL;
	230	current = to_resend;
	231	while(current) {
	232	if(resend_expired(current)) {
	233	if(previous == NULL) {
	234	to_resend = current->next;
	235	free(current);
	236	current = to_resend;
	237	} else {
	238	previous->next = current->next;
	239	free(current);
	240	current = previous->next;
	241	}
	242	recompute = 1;
	243	} else {
	244	previous = current;
	245	current = current->next;
	246	}
	247	}
	248	if(recompute)
	249	recompute_resend_time();
	250	}
	251
	252	void
4d762f26	253	recompute_resend_time(void)
ca10883e DS	254	{
	255	struct resend *request;
	256	struct timeval resend = {0, 0};
	257
	258	request = to_resend;
	259	while(request) {
	260	if(!resend_expired(request) && request->delay > 0 && request->max > 0) {
	261	struct timeval timeout;
	262	timeval_add_msec(&timeout, &request->time, request->delay);
	263	timeval_min(&resend, &timeout);
	264	}
	265	request = request->next;
	266	}
	267
	268	resend_time = resend;
	269	}
	270
	271	void
4d762f26	272	do_resend(void)
ca10883e DS	273	{
	274	struct resend *resend;
	275
	276	resend = to_resend;
	277	while(resend) {
	278	if(!resend_expired(resend) && resend->delay > 0 && resend->max > 0) {
	279	struct timeval timeout;
	280	timeval_add_msec(&timeout, &resend->time, resend->delay);
	281	if(timeval_compare(&babel_now, &timeout) >= 0) {
	282	switch(resend->kind) {
	283	case RESEND_REQUEST:
	284	send_multihop_request(resend->ifp,
	285	resend->prefix, resend->plen,
	286	resend->seqno, resend->id, 127);
	287	break;
	288	case RESEND_UPDATE:
	289	send_update(resend->ifp, 1,
	290	resend->prefix, resend->plen);
	291	break;
	292	default: abort();
	293	}
	294	resend->delay = MIN(0xFFFF, resend->delay * 2);
	295	resend->max--;
	296	}
	297	}
	298	resend = resend->next;
	299	}
	300	recompute_resend_time();
	301	}