rrl.h 4.98 KB
Newer Older
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
/*  Copyright (C) 2011 CZ.NIC, z.s.p.o. <knot-dns@labs.nic.cz>

    This program is free software: you can redistribute it and/or modify
    it under the terms of the GNU General Public License as published by
    the Free Software Foundation, either version 3 of the License, or
    (at your option) any later version.

    This program is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    GNU General Public License for more details.

    You should have received a copy of the GNU General Public License
    along with this program.  If not, see <http://www.gnu.org/licenses/>.
 */
/*!
 * \file rrl.h
 *
 * \author Marek Vavrusa <marek.vavusa@nic.cz>
 *
 * \brief Response-rate limiting API.
 *
 * \addtogroup network
 * @{
 */

27
#pragma once
28 29

#include <stdint.h>
30
#include <pthread.h>
31
#include "libknot/internal/sockaddr.h"
32
#include "libknot/packet/pkt.h"
33

34
/* Defaults */
35
#define RRL_SLIP_MAX 100
36
#define RRL_LOCK_GRANULARITY 32 /* Last digit granularity */
37

38 39 40 41 42 43
/*! \brief RRL flags. */
enum {
	RRL_NOFLAG    = 0 << 0, /*!< No flags. */
	RRL_WILDCARD  = 1 << 1  /*!< Query to wildcard name. */
};

44
struct zone;
45

46 47 48
/*!
 * \brief RRL hash bucket.
 */
49
typedef struct rrl_item {
50
	unsigned hop;        /* Hop bitmap. */
51
	uint64_t netblk;     /* Prefix associated. */
52 53 54
	uint16_t ntok;       /* Tokens available */
	uint8_t  cls;        /* Bucket class */
	uint8_t  flags;      /* Flags */
55
	uint32_t qname;      /* imputed(QNAME) hash */
56 57 58
	uint32_t time;       /* Timestamp */
} rrl_item_t;

59 60
/*!
 * \brief RRL hash bucket table.
Jan Včelák's avatar
Jan Včelák committed
61
 *
62 63 64 65 66 67 68 69
 * Table is fixed size, so collisions may occur and are dealt with
 * in a way, that hashbucket rate is reset and enters slow-start for 1 dt.
 * When a bucket is in a slow-start mode, it cannot reset again for the time
 * period.
 *
 * To avoid lock contention, N locks are created and distributed amongst buckets.
 * As of now lock K for bucket N is calculated as K = N % (num_buckets).
 */
Jan Včelák's avatar
Jan Včelák committed
70

71
typedef struct rrl_table {
72
	uint32_t rate;       /* Configured RRL limit */
73
	uint32_t seed;       /* Pseudorandom seed for hashing. */
74 75 76
	pthread_mutex_t ll;
	pthread_mutex_t *lk;      /* Table locks. */
	unsigned lk_count;   /* Table lock count (granularity). */
77 78 79 80
	size_t size;         /* Number of buckets */
	rrl_item_t arr[];    /* Buckets */
} rrl_table_t;

81 82 83
/*!
 * \brief RRL request descriptor.
 */
84 85 86 87
typedef struct rrl_req {
	const uint8_t *w;
	uint16_t len;
	unsigned flags;
88
	knot_pkt_t *query;
89 90
} rrl_req_t;

91 92 93 94 95
/*!
 * \brief Create a RRL table.
 * \param size Fixed hashtable size (reasonable large prime is recommended).
 * \return created table or NULL.
 */
96
rrl_table_t *rrl_create(size_t size);
97 98 99 100 101 102

/*!
 * \brief Get RRL table default rate.
 * \param rrl RRL table.
 * \return rate
 */
103
uint32_t rrl_rate(rrl_table_t *rrl);
104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123

/*!
 * \brief Set RRL table default rate.
 *
 * \note When changing the rate, it is NOT applied to all buckets immediately.
 *
 * \param rrl RRL table.
 * \param rate New rate (in pkts/sec).
 * \return old rate
 */
uint32_t rrl_setrate(rrl_table_t *rrl, uint32_t rate);

/*!
 * \brief Set N distributed locks for the RRL table.
 *
 * \param rrl RRL table.
 * \param granularity Number of created locks.
 * \retval KNOT_EOK
 * \retval KNOT_EINVAL
 */
124
int rrl_setlocks(rrl_table_t *rrl, unsigned granularity);
125

126 127 128 129 130 131 132
/*!
 * \brief Get bucket for current combination of parameters.
 * \param t RRL table.
 * \param a Source address.
 * \param p RRL request.
 * \param zone Relate zone.
 * \param stamp Timestamp (current time).
133
 * \param lock Held lock.
134 135
 * \return assigned bucket
 */
136
rrl_item_t* rrl_hash(rrl_table_t *t, const struct sockaddr_storage *a, rrl_req_t *p,
137
                     const struct zone *zone, uint32_t stamp, int* lock);
138

139 140 141 142 143 144 145 146 147 148
/*!
 * \brief Query the RRL table for accept or deny, when the rate limit is reached.
 *
 * \param rrl RRL table.
 * \param a Source address.
 * \param req RRL request (containing resp., flags and question).
 * \param zone Zone related to the response (or NULL).
 * \retval KNOT_EOK if passed.
 * \retval KNOT_ELIMIT when the limit is reached.
 */
149
int rrl_query(rrl_table_t *rrl, const struct sockaddr_storage *a, rrl_req_t *req,
150
              const struct zone *zone);
151

152 153 154 155 156 157 158
/*!
 * \brief Roll a dice whether answer slips or not.
 * \param n_slip Number represents every Nth answer that is slipped.
 * \return true or false
 */
bool rrl_slip_roll(int n_slip);

159 160 161
/*!
 * \brief Destroy RRL table.
 * \param rrl RRL table.
Jan Včelák's avatar
Jan Včelák committed
162
 * \return KNOT_EOK
163
 */
164 165
int rrl_destroy(rrl_table_t *rrl);

166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189
/*!
 * \brief Reseed RRL table secret.
 * \param rrl RRL table.
 * \return KNOT_EOK
 */
int rrl_reseed(rrl_table_t *rrl);

/*!
 * \brief Lock specified element lock.
 * \param rrl RRL table.
 * \param lk_id Specified lock.
 * \retval KNOT_EOK
 * \retval KNOT_ERROR
 */
int rrl_lock(rrl_table_t *rrl, int lk_id);

/*!
 * \brief Unlock specified element lock.
 * \param rrl RRL table.
 * \param lk_id Specified lock.
 * \retval KNOT_EOK
 * \retval KNOT_ERROR
 */
int rrl_unlock(rrl_table_t *rrl, int lk_id);
190 191

/*! @} */