Knot DNS Resolver library¶
For users¶
The library as described provides basic services for name resolution, which should cover the usage, examples are in the resolve API documentation.
Tip
If you’re migrating from getaddrinfo()
, see “synchronous” API, but the library offers iterative API as well to plug it into your event loop for example.
For developers¶
The resolution process starts with the functions in resolve.c, they are responsible for:
- reacting to state machine state (i.e. calling consume layers if we have an answer ready)
- interacting with the library user (i.e. asking caller for I/O, accepting queries)
- fetching assets needed by layers (i.e. zone cut)
This is the driver. The driver is not meant to know “how” the query resolves, but rather “when” to execute “what”.
On the other side are layers. They are responsible for dissecting the packets and informing the driver about the results. For example, a produce layer generates query, a consume layer validates answer.
Tip
Layers are executed asynchronously by the driver. If you need some asset beforehand, you can signalize the driver using returning state or current query flags. For example, setting a flag AWAIT_CUT
forces driver to fetch zone cut information before the packet is consumed; setting a RESOLVED
flag makes it pop a query after the current set of layers is finished; returning FAIL
state makes it fail current query.
Layers can also change course of resolution, for example by appending additional queries.
consume = function (state, req, answer)
answer = kres.pkt_t(answer)
if answer:qtype() == kres.type.NS then
req = kres.request_t(req)
local qry = req:push(answer:qname(), kres.type.SOA, kres.class.IN)
qry.flags.AWAIT_CUT = true
end
return state
end
This doesn’t block currently processed query, and the newly created sub-request will start as soon as driver finishes processing current. In some cases you might need to issue sub-request and process it before continuing with the current, i.e. validator may need a DNSKEY before it can validate signatures. In this case, layers can yield and resume afterwards.
consume = function (state, req, answer)
answer = kres.pkt_t(answer)
if state == kres.YIELD then
print('continuing yielded layer')
return kres.DONE
else
if answer:qtype() == kres.type.NS then
req = kres.request_t(req)
local qry = req:push(answer:qname(), kres.type.SOA, kres.class.IN)
qry.flags.AWAIT_CUT = true
print('planned SOA query, yielding')
return kres.YIELD
end
return state
end
end
The YIELD
state is a bit special. When a layer returns it, it interrupts current walk through the layers. When the layer receives it,
it means that it yielded before and now it is resumed. This is useful in a situation where you need a sub-request to determine whether current answer is valid or not.
Writing layers¶
Warning
FIXME: this dev-docs section is outdated! Better see comments in files instead, for now.
The resolver library leverages the processing API from the libknot to separate packet processing code into layers.
Note
This is only crash-course in the library internals, see the resolver library documentation for the complete overview of the services.
The library offers following services:
- Cache - MVCC cache interface for retrieving/storing resource records.
- Resolution plan - Query resolution plan, a list of partial queries (with hierarchy) sent in order to satisfy original query. This contains information about the queries, nameserver choice, timing information, answer and its class.
- Nameservers - Reputation database of nameservers, this serves as an aid for nameserver choice.
A processing layer is going to be called by the query resolution driver for each query, so you’re going to work with struct kr_request as your per-query context. This structure contains pointers to resolution context, resolution plan and also the final answer.
int consume(kr_layer_t *ctx, knot_pkt_t *pkt)
{
struct kr_request *req = ctx->req;
struct kr_query *qry = req->current_query;
}
This is only passive processing of the incoming answer. If you want to change the course of resolution, say satisfy a query from a local cache before the library issues a query to the nameserver, you can use states (see the Static hints for example).
int produce(kr_layer_t *ctx, knot_pkt_t *pkt)
{
struct kr_request *req = ctx->req;
struct kr_query *qry = req->current_query;
/* Query can be satisfied locally. */
if (can_satisfy(qry)) {
/* This flag makes the resolver move the query
* to the "resolved" list. */
qry->flags.RESOLVED = true;
return KR_STATE_DONE;
}
/* Pass-through. */
return ctx->state;
}
It is possible to not only act during the query resolution, but also to view the complete resolution plan afterwards. This is useful for analysis-type tasks, or “per answer” hooks.
int finish(kr_layer_t *ctx)
{
struct kr_request *req = ctx->req;
struct kr_rplan *rplan = req->rplan;
/* Print the query sequence with start time. */
char qname_str[KNOT_DNAME_MAXLEN];
struct kr_query *qry = NULL
WALK_LIST(qry, rplan->resolved) {
knot_dname_to_str(qname_str, qry->sname, sizeof(qname_str));
printf("%s at %u\n", qname_str, qry->timestamp);
}
return ctx->state;
}
APIs in Lua¶
The APIs in Lua world try to mirror the C APIs using LuaJIT FFI, with several differences and enhancements. There is not comprehensive guide on the API yet, but you can have a look at the bindings file.
Elementary types and constants¶
- States are directly in
kres
table, e.g.kres.YIELD, kres.CONSUME, kres.PRODUCE, kres.DONE, kres.FAIL
. - DNS classes are in
kres.class
table, e.g.kres.class.IN
for Internet class. - DNS types are in
kres.type
table, e.g.kres.type.AAAA
for AAAA type. - DNS rcodes types are in
kres.rcode
table, e.g.kres.rcode.NOERROR
. - Packet sections (QUESTION, ANSWER, AUTHORITY, ADDITIONAL) are in the
kres.section
table.
Working with domain names¶
The internal API usually works with domain names in label format, you can convert between text and wire freely.
local dname = kres.str2dname('business.se')
local strname = kres.dname2str(dname)
Working with resource records¶
Resource records are stored as tables.
local rr = { owner = kres.str2dname('owner'),
ttl = 0,
class = kres.class.IN,
type = kres.type.CNAME,
rdata = kres.str2dname('someplace') }
print(kres.rr2str(rr))
RRSets in packet can be accessed using FFI, you can easily fetch single records.
local rrset = { ... }
local rr = rrset:get(0) -- Return first RR
print(kres.dname2str(rr:owner()))
print(rr:ttl())
print(kres.rr2str(rr))
Working with packets¶
Packet is the data structure that you’re going to see in layers very often. They consists of a header, and four sections: QUESTION, ANSWER, AUTHORITY, ADDITIONAL. The first section is special, as it contains the query name, type, and class; the rest of the sections contain RRSets.
First you need to convert it to a type known to FFI and check basic properties. Let’s start with a snippet of a consume layer.
consume = function (state, req, pkt)
pkt = kres.pkt_t(answer)
print('rcode:', pkt:rcode())
print('query:', kres.dname2str(pkt:qname()), pkt:qclass(), pkt:qtype())
if pkt:rcode() ~= kres.rcode.NOERROR then
print('error response')
end
end
You can enumerate records in the sections.
local records = pkt:section(kres.section.ANSWER)
for i = 1, #records do
local rr = records[i]
if rr.type == kres.type.AAAA then
print(kres.rr2str(rr))
end
end
During produce or begin, you might want to want to write to packet. Keep in mind that you have to write packet sections in sequence, e.g. you can’t write to ANSWER after writing AUTHORITY, it’s like stages where you can’t go back.
pkt:rcode(kres.rcode.NXDOMAIN)
-- Clear answer and write QUESTION
pkt:clear()
pkt:question('\7blocked', kres.class.IN, kres.type.SOA)
-- Start writing data
pkt:begin(kres.section.ANSWER)
-- Nothing in answer
pkt:begin(kres.section.AUTHORITY)
local soa = { owner = '\7blocked', ttl = 900, class = kres.class.IN, type = kres.type.SOA, rdata = '...' }
pkt:put(soa.owner, soa.ttl, soa.class, soa.type, soa.rdata)
Working with requests¶
The request holds information about currently processed query, enabled options, cache, and other extra data. You primarily need to retrieve currently processed query.
consume = function (state, req, pkt)
req = kres.request_t(req)
print(req.options)
print(req.state)
-- Print information about current query
local current = req:current()
print(kres.dname2str(current.owner))
print(current.stype, current.sclass, current.id, current.flags)
end
In layers that either begin or finalize, you can walk the list of resolved queries.
local last = req:resolved()
print(last.stype)
As described in the layers, you can not only retrieve information about current query, but also push new ones or pop old ones.
-- Push new query
local qry = req:push(pkt:qname(), kres.type.SOA, kres.class.IN)
qry.flags.AWAIT_CUT = true
-- Pop the query, this will erase it from resolution plan
req:pop(qry)
API reference¶
Name resolution¶
The API provides an API providing a “consumer-producer”-like interface to enable user to plug it into existing event loop or I/O code.
Example usage of the iterative API:
// Create request and its memory pool
struct kr_request req = {
.pool = {
.ctx = mp_new (4096),
.alloc = (mm_alloc_t) mp_alloc
}
};
// Setup and provide input query
int state = kr_resolve_begin(&req, ctx, final_answer);
state = kr_resolve_consume(&req, query);
// Generate answer
while (state == KR_STATE_PRODUCE) {
// Additional query generate, do the I/O and pass back answer
state = kr_resolve_produce(&req, &addr, &type, query);
while (state == KR_STATE_CONSUME) {
int ret = sendrecv(addr, proto, query, resp);
// If I/O fails, make "resp" empty
state = kr_resolve_consume(&request, addr, resp);
knot_pkt_clear(resp);
}
knot_pkt_clear(query);
}
// "state" is either DONE or FAIL
kr_resolve_finish(&request, state);
Enums
- kr_rank enum
RRset rank - for cache and ranked_rr_*.
The rank meaning consists of one independent flag - KR_RANK_AUTH, and the rest have meaning of values where only one can hold at any time. You can use one of the enums as a safe initial value, optionally | KR_RANK_AUTH; otherwise it’s best to manipulate ranks via the kr_rank_* functions.
See also: https://tools.ietf.org/html/rfc2181#section-5.4.1 https://tools.ietf.org/html/rfc4035#section-4.3
- Note
- The representation is complicated by restrictions on integer comparison:
- AUTH must be > than !AUTH
- AUTH INSECURE must be > than AUTH (because it attempted validation)
- !AUTH SECURE must be > than AUTH (because it’s valid)
Values:
KR_RANK_INITIAL
= = 0
-Did not attempt to validate.
It’s assumed compulsory to validate (or prove insecure).
KR_RANK_OMIT
-Do not attempt to validate.
(And don’t consider it a validation failure.)
KR_RANK_TRY
-Attempt to validate, but failures are non-fatal.
KR_RANK_INDET
= = 4
-Unable to determine whether it should be secure.
KR_RANK_BOGUS
-Ought to be secure but isn’t.
KR_RANK_MISMATCH
-KR_RANK_MISSING
-Unable to obtain a good signature.
KR_RANK_INSECURE
= = 8
-Proven to be insecure.
KR_RANK_AUTH
= = 16
-Authoritative data flag; the chain of authority was “verified”.
Even if not set, only in-bailiwick stuff is acceptable, i.e. almost authoritative (example: mandatory glue and its NS RR).
KR_RANK_SECURE
= = 32
-Verified whole chain of trust from the closest TA.
Functions
-
bool
kr_rank_check
(uint8_t rank) Check that a rank value is valid.
Meant for assertions.
-
bool
kr_rank_test
(uint8_t rank, uint8_t kr_flag) Test the presence of any flag/state in a rank, i.e.
including KR_RANK_AUTH.
-
void
kr_rank_set
(uint8_t * rank, uint8_t kr_flag) Set the rank state.
The _AUTH flag is kept as it was.
-
KR_EXPORT int
kr_resolve_begin
(struct kr_request * request, struct kr_context * ctx, knot_pkt_t * answer) Begin name resolution.
- Note
- Expects a request to have an initialized mempool, the “answer” packet will be kept during the resolution and will contain the final answer at the end.
- Return
- CONSUME (expecting query)
- Parameters
request
-request state with initialized mempool
ctx
-resolution context
answer
-allocated packet for final answer
-
KR_EXPORT int
kr_resolve_consume
(struct kr_request * request, const struct sockaddr * src, knot_pkt_t * packet) Consume input packet (may be either first query or answer to query originated from kr_resolve_produce())
- Note
- If the I/O fails, provide an empty or NULL packet, this will make iterator recognize nameserver failure.
- Return
- any state
- Parameters
request
-request state (awaiting input)
src
-[in] packet source address
packet
-[in] input packet
-
KR_EXPORT int
kr_resolve_produce
(struct kr_request * request, struct sockaddr ** dst, int * type, knot_pkt_t * packet) Produce either next additional query or finish.
If the CONSUME is returned then dst, type and packet will be filled with appropriate values and caller is responsible to send them and receive answer. If it returns any other state, then content of the variables is undefined.
- Return
- any state
- Parameters
request
-request state (in PRODUCE state)
dst
-[out] possible address of the next nameserver
type
-[out] possible used socket type (SOCK_STREAM, SOCK_DGRAM)
packet
-[out] packet to be filled with additional query
-
KR_EXPORT int
kr_resolve_checkout
(struct kr_request * request, struct sockaddr * src, struct sockaddr * dst, int type, knot_pkt_t * packet) Finalises the outbound query packet with the knowledge of the IP addresses.
- Note
- The function must be called before actual sending of the request packet.
- Return
- kr_ok() or error code
- Parameters
request
-request state (in PRODUCE state)
src
-address from which the query is going to be sent
dst
-address of the name server
type
-used socket type (SOCK_STREAM, SOCK_DGRAM)
packet
-[in,out] query packet to be finalised
-
KR_EXPORT int
kr_resolve_finish
(struct kr_request * request, int state) Finish resolution and commit results if the state is DONE.
- Note
- The structures will be deinitialized, but the assigned memory pool is not going to be destroyed, as it’s owned by caller.
- Return
- DONE
- Parameters
request
-request state
state
-either DONE or FAIL state
-
KR_EXPORT KR_PURE struct kr_rplan *
kr_resolve_plan
(struct kr_request * request) Return resolution plan.
- Return
- pointer to rplan
- Parameters
request
-request state
-
KR_EXPORT KR_PURE knot_mm_t *
kr_resolve_pool
(struct kr_request * request) Return memory pool associated with request.
- Return
- mempool
- Parameters
request
-request state
-
struct
kr_context
- #include <resolve.h>
Name resolution context.
Resolution context provides basic services like cache, configuration and options.
- Note
- This structure is persistent between name resolutions and may be shared between threads.
Public Members
-
struct kr_qflags
options
-
knot_rrset_t *
opt_rr
-
map_t
trust_anchors
-
map_t
negative_anchors
-
struct kr_zonecut
root_hints
-
struct kr_cache
cache
-
kr_nsrep_lru_t *
cache_rtt
-
kr_nsrep_lru_t *
cache_rep
-
module_array_t *
modules
-
struct kr_cookie_ctx
cookie_ctx
-
kr_cookie_lru_t *
cache_cookie
-
int32_t
tls_padding
See net.tls_padding in ../daemon/README.rst -1 is “true” (default policy), 0 is “false” (no padding)
-
knot_mm_t *
pool
-
struct
kr_request
- #include <resolve.h>
Name resolution request.
Keeps information about current query processing between calls to processing APIs, i.e. current resolved query, resolution plan, ... Use this instead of the simple interface if you want to implement multiplexing or custom I/O.
- Note
- All data for this request must be allocated from the given pool.
Public Members
-
struct kr_context *
ctx
-
knot_pkt_t *
answer
-
struct kr_query *
current_query
Current evaluated query.
-
const knot_rrset_t *
key
-
const struct sockaddr *
addr
Current upstream address.
-
const struct sockaddr *
dst_addr
-
const knot_pkt_t *
packet
-
const knot_rrset_t *
opt
-
bool
tcp
true if the request is on tcp; only meaningful if (dst_addr)
-
struct kr_request::@2
qsource
-
unsigned
rtt
Current upstream RTT.
-
struct kr_request::@3
upstream
Upstream information, valid only in consume() phase.
-
struct kr_qflags
options
-
int
state
-
ranked_rr_array_t
answ_selected
-
ranked_rr_array_t
auth_selected
-
rr_array_t
additional
-
bool
answ_validated
internal to validator; beware of caching, etc.
-
bool
auth_validated
see answ_validated ^^ ; TODO
-
struct kr_rplan
rplan
-
int
has_tls
-
knot_mm_t
pool
Functions
-
KR_EXPORT void
kr_qflags_set
(struct kr_qflags * fl1, struct kr_qflags fl2) Combine flags together.
This means set union for simple flags.
-
KR_EXPORT void
kr_qflags_clear
(struct kr_qflags * fl1, struct kr_qflags fl2) Remove flags.
This means set-theoretic difference.
-
KR_EXPORT int
kr_rplan_init
(struct kr_rplan * rplan, struct kr_request * request, knot_mm_t * pool) Initialize resolution plan (empty).
- Parameters
rplan
-plan instance
request
-resolution request
pool
-ephemeral memory pool for whole resolution
-
KR_EXPORT void
kr_rplan_deinit
(struct kr_rplan * rplan) Deinitialize resolution plan, aborting any uncommited transactions.
- Parameters
rplan
-plan instance
-
KR_EXPORT KR_PURE bool
kr_rplan_empty
(struct kr_rplan * rplan) Return true if the resolution plan is empty (i.e.
finished or initialized)
- Return
- true or false
- Parameters
rplan
-plan instance
-
KR_EXPORT struct kr_query *
kr_rplan_push_empty
(struct kr_rplan * rplan, struct kr_query * parent) Push empty query to the top of the resolution plan.
- Note
- This query serves as a cookie query only.
- Return
- query instance or NULL
- Parameters
rplan
-plan instance
parent
-query parent (or NULL)
-
KR_EXPORT struct kr_query *
kr_rplan_push
(struct kr_rplan * rplan, struct kr_query * parent, const knot_dname_t * name, uint16_t cls, uint16_t type) Push a query to the top of the resolution plan.
- Note
- This means that this query takes precedence before all pending queries.
- Return
- query instance or NULL
- Parameters
rplan
-plan instance
parent
-query parent (or NULL)
name
-resolved name
cls
-resolved class
type
-resolved type
-
KR_EXPORT int
kr_rplan_pop
(struct kr_rplan * rplan, struct kr_query * qry) Pop existing query from the resolution plan.
- Note
- Popped queries are not discarded, but moved to the resolved list.
- Return
- 0 or an error
- Parameters
rplan
-plan instance
qry
-resolved query
-
KR_EXPORT KR_PURE bool
kr_rplan_satisfies
(struct kr_query * closure, const knot_dname_t * name, uint16_t cls, uint16_t type) Return true if resolution chain satisfies given query.
-
KR_EXPORT KR_PURE struct kr_query *
kr_rplan_resolved
(struct kr_rplan * rplan) Return last resolved query.
-
KR_EXPORT KR_PURE struct kr_query *
kr_rplan_find_resolved
(struct kr_rplan * rplan, struct kr_query * parent, const knot_dname_t * name, uint16_t cls, uint16_t type) Check if a given query already resolved.
- Return
- query instance or NULL
- Parameters
rplan
-plan instance
parent
-query parent (or NULL)
name
-resolved name
cls
-resolved class
type
-resolved type
-
struct
kr_qflags
- #include <rplan.h>
Query flags.
Public Members
-
bool
NO_MINIMIZE
Don’t minimize QNAME.
-
bool
NO_THROTTLE
No query/slow NS throttling.
-
bool
NO_IPV6
Disable IPv6.
-
bool
NO_IPV4
Disable IPv4.
-
bool
TCP
Use TCP for this query.
-
bool
RESOLVED
Query is resolved.
-
bool
AWAIT_IPV4
Query is waiting for A address.
-
bool
AWAIT_IPV6
Query is waiting for AAAA address.
-
bool
AWAIT_CUT
Query is waiting for zone cut lookup.
-
bool
SAFEMODE
Don’t use fancy stuff (EDNS, 0x20, ...)
-
bool
CACHED
Query response is cached.
-
bool
NO_CACHE
No cache for lookup; exception: finding NSs and subqueries.
-
bool
EXPIRING
Query response is cached, but expiring.
-
bool
ALLOW_LOCAL
Allow queries to local or private address ranges.
-
bool
DNSSEC_WANT
Want DNSSEC secured answer; exception: +cd, i.e.
knot_wire_set_cd(request->answer->wire).
-
bool
DNSSEC_BOGUS
Query response is DNSSEC bogus.
-
bool
DNSSEC_INSECURE
Query response is DNSSEC insecure.
-
bool
DNSSEC_CD
CD bit in query.
-
bool
STUB
Stub resolution, accept received answer as solved.
-
bool
ALWAYS_CUT
Always recover zone cut (even if cached).
-
bool
DNSSEC_WEXPAND
Query response has wildcard expansion.
-
bool
PERMISSIVE
Permissive resolver mode.
-
bool
STRICT
Strict resolver mode.
-
bool
BADCOOKIE_AGAIN
Query again because bad cookie returned.
-
bool
CNAME
Query response contains CNAME in answer section.
-
bool
REORDER_RR
Reorder cached RRs.
-
bool
TRACE
Log answer with kr_verbose_log(), unless -DNDEBUG.
-
bool
NO_0X20
Disable query case randomization .
-
bool
DNSSEC_NODS
DS non-existance is proven.
-
bool
DNSSEC_OPTOUT
Closest encloser proof has optout.
-
bool
NONAUTH
Non-authoritative in-bailiwick records are enough.
TODO: utilize this also outside cache.
-
bool
FORWARD
Forward all queries to upstream; validate answers.
-
bool
DNS64_MARK
Internal mark for dns64 module.
-
bool
-
struct
kr_query
- #include <rplan.h>
Single query representation.
Public Members
-
struct kr_query *
parent
-
knot_dname_t *
sname
-
uint16_t
stype
-
uint16_t
sclass
-
uint16_t
id
-
struct kr_qflags flags
forward_flags
-
uint32_t
secret
-
uint16_t
fails
-
uint16_t
reorder
Seed to reorder (cached) RRs in answer or zero.
-
uint64_t
creation_time_mono
-
uint64_t
timestamp_mono
Time of query created or time of query to upstream resolver (milliseconds).
-
struct timeval
timestamp
-
struct kr_zonecut
zone_cut
-
struct kr_nsrep
ns
-
struct kr_layer_pickle *
deferred
-
uint32_t
uid
Query iteration number, unique within the kr_rplan.
-
struct kr_query *
cname_parent
Pointer to the query that originated this one because of following a CNAME (or NULL).
-
struct kr_query *
-
struct
kr_rplan
- #include <rplan.h>
Query resolution plan structure.
The structure most importantly holds the original query, answer and the list of pending queries required to resolve the original query. It also keeps a notion of current zone cut.
Public Members
-
kr_qarray_t
pending
List of pending queries.
-
kr_qarray_t
resolved
List of resolved queries.
-
struct kr_request *
request
Parent resolution request.
-
knot_mm_t *
pool
Temporary memory pool.
-
uint32_t
next_uid
Next value for kr_query::uid (incremental).
-
kr_qarray_t
Cache¶
Enums
- kr_cache_tag enum
Cache entry tag.
Values:
KR_CACHE_RR
= = 'R'
-KR_CACHE_PKT
= = 'P'
-KR_CACHE_SIG
= = 'G'
-KR_CACHE_USER
= = 0x80
-
- kr_cache_flag enum
Cache entry flags.
Values:
KR_CACHE_FLAG_NONE
= = 0
-KR_CACHE_FLAG_WCARD_PROOF
= = 1
-KR_CACHE_FLAG_OPTOUT
= = 2
-KR_CACHE_FLAG_NODS
= = 4
-
Functions
-
KR_EXPORT int
kr_cache_open
(struct kr_cache * cache, const struct kr_cdb_api * api, struct kr_cdb_opts * opts, knot_mm_t * mm) Open/create cache with provided storage options.
- Return
- 0 or an error code
- Parameters
cache
-cache structure to be initialized
api
-storage engine API
opts
-storage-specific options (may be NULL for default)
mm
-memory context.
-
KR_EXPORT void
kr_cache_close
(struct kr_cache * cache) Close persistent cache.
- Note
- This doesn’t clear the data, just closes the connection to the database.
- Parameters
cache
-structure
-
KR_EXPORT int
kr_cache_sync
(struct kr_cache * cache) Run after a row of operations to release transaction/lock if needed.
-
bool
kr_cache_is_open
(struct kr_cache * cache) Return true if cache is open and enabled.
-
KR_EXPORT int
kr_cache_peek
(struct kr_cache * cache, uint8_t tag, const knot_dname_t * name, uint16_t type, struct kr_cache_entry ** entry, uint32_t * timestamp) Peek the cache for asset (name, type, tag)
- Note
- The ‘drift’ is the time passed between the inception time and now (in seconds).
- Return
- 0 or an errcode
- Parameters
cache
-cache structure
tag
-asset tag
name
-asset name
type
-asset type
entry
-cache entry, will be set to valid pointer or NULL
timestamp
-current time (will be replaced with drift if successful)
-
KR_EXPORT int
kr_cache_insert
(struct kr_cache * cache, uint8_t tag, const knot_dname_t * name, uint16_t type, struct kr_cache_entry * header, knot_db_val_t data) Insert asset into cache, replacing any existing data.
- Return
- 0 or an errcode
- Parameters
cache
-cache structure
tag
-asset tag
name
-asset name
type
-asset type
header
-filled entry header (count, ttl and timestamp)
data
-inserted data
-
KR_EXPORT int
kr_cache_remove
(struct kr_cache * cache, uint8_t tag, const knot_dname_t * name, uint16_t type) Remove asset from cache.
- Return
- 0 or an errcode
- Parameters
cache
-cache structure
tag
-asset tag
name
-asset name
type
-record type
-
KR_EXPORT int
kr_cache_clear
(struct kr_cache * cache) Clear all items from the cache.
- Return
- 0 or an errcode
- Parameters
cache
-cache structure
-
KR_EXPORT int
kr_cache_match
(struct kr_cache * cache, uint8_t tag, const knot_dname_t * name, knot_db_val_t * vals, int valcnt) Prefix scan on cached items.
- Return
- number of retrieved keys or an error
- Parameters
cache
-cache structure
tag
-asset tag
name
-asset prefix key
vals
-array of values to store the result
valcnt
-maximum number of retrieved keys
-
KR_EXPORT int
kr_cache_peek_rank
(struct kr_cache * cache, uint8_t tag, const knot_dname_t * name, uint16_t type, uint32_t timestamp) Peek the cache for given key and retrieve it’s rank.
- Return
- rank (0 or positive), or an error (negative number)
- Parameters
cache
-cache structure
tag
-asset tag
name
-asset name
type
-record type
timestamp
-current time
-
KR_EXPORT int
kr_cache_peek_rr
(struct kr_cache * cache, knot_rrset_t * rr, uint8_t * rank, uint8_t * flags, uint32_t * timestamp) Peek the cache for given RRSet (name, type)
- Note
- The ‘drift’ is the time passed between the cache time of the RRSet and now (in seconds).
- Return
- 0 or an errcode
- Parameters
cache
-cache structure
rr
-query RRSet (its rdataset may be changed depending on the result)
rank
-entry rank will be stored in this variable
flags
-entry flags
timestamp
-current time (will be replaced with drift if successful)
-
KR_EXPORT int
kr_cache_materialize
(knot_rrset_t * dst, const knot_rrset_t * src, uint32_t drift, uint reorder, knot_mm_t * mm) Clone read-only RRSet and adjust TTLs.
- Return
- 0 or an errcode
- Parameters
dst
-destination for materialized RRSet
src
-read-only RRSet (its rdataset may be changed depending on the result)
drift
-time passed between cache time and now
reorder
-(pseudo)-random seed to reorder the data or zero
mm
-memory context
-
KR_EXPORT int
kr_cache_insert_rr
(struct kr_cache * cache, const knot_rrset_t * rr, uint8_t rank, uint8_t flags, uint32_t timestamp) Insert RRSet into cache, replacing any existing data.
- Return
- 0 or an errcode
- Parameters
cache
-cache structure
rr
-inserted RRSet
rank
-rank of the data
flags
-additional flags for the data
timestamp
-current time
-
KR_EXPORT int
kr_cache_peek_rrsig
(struct kr_cache * cache, knot_rrset_t * rr, uint8_t * rank, uint8_t * flags, uint32_t * timestamp) Peek the cache for the given RRset signature (name, type)
- Note
- The RRset type must not be RRSIG but instead it must equal the type covered field of the sought RRSIG.
- Return
- 0 or an errcode
- Parameters
cache
-cache structure
rr
-query RRSET (its rdataset and type may be changed depending on the result)
rank
-entry rank will be stored in this variable
flags
-entry additional flags
timestamp
-current time (will be replaced with drift if successful)
-
KR_EXPORT int
kr_cache_insert_rrsig
(struct kr_cache * cache, const knot_rrset_t * rr, uint8_t rank, uint8_t flags, uint32_t timestamp) Insert the selected RRSIG RRSet of the selected type covered into cache, replacing any existing data.
- Note
- The RRSet must contain RRSIGS with only the specified type covered.
- Return
- 0 or an errcode
- Parameters
cache
-cache structure
rr
-inserted RRSIG RRSet
rank
-rank of the data
flags
-additional flags for the data
timestamp
-current time
Variables
-
const size_t
PKT_SIZE_NOWIRE
When knot_pkt is passed from cache without ->wire, this is the ->size.
-
struct
kr_cache_entry
- #include <cache.h>
Serialized form of the RRSet with inception timestamp and maximum TTL.
Public Members
-
uint32_t
timestamp
-
uint32_t
ttl
-
uint16_t
count
-
uint8_t
rank
-
uint8_t
flags
-
uint8_t
data
[]
-
uint32_t
-
struct
kr_cache
- #include <cache.h>
Cache structure, keeps API, instance and metadata.
Public Members
-
knot_db_t *
db
Storage instance.
-
const struct kr_cdb_api *
api
Storage engine.
-
uint32_t
hit
Number of cache hits.
-
uint32_t
miss
Number of cache misses.
-
uint32_t
insert
Number of insertions.
-
uint32_t
delete
Number of deletions.
-
struct kr_cache::@0
stats
-
uint32_t
ttl_min
-
uint32_t
ttl_max
Maximum TTL of inserted entries.
-
struct timeval
last_clear_walltime
Time of last cache clear.
-
uint64_t
last_clear_monotime
Last cache clear in monotonic milliseconds.
-
knot_db_t *
Nameservers¶
Defines
- KR_NSREP_MAXADDR
Enums
- kr_ns_score enum
NS RTT score (special values).
- Note
- RTT is measured in milliseconds.
Values:
KR_NS_MAX_SCORE
= = KR_CONN_RTT_MAX
-KR_NS_TIMEOUT
= = (95 * KR_NS_MAX_SCORE) / 100
-KR_NS_LONG
= = (3 * KR_NS_TIMEOUT) / 4
-KR_NS_UNKNOWN
= = KR_NS_TIMEOUT / 2
-KR_NS_PENALTY
= = 100
-KR_NS_GLUED
= = 10
-
- kr_ns_rep enum
NS QoS flags.
Values:
KR_NS_NOIP4
= = 1 << 0
-NS has no IPv4.
KR_NS_NOIP6
= = 1 << 1
-NS has no IPv6.
KR_NS_NOEDNS
= = 1 << 2
-NS has no EDNS support.
- kr_ns_update_mode enum
NS RTT update modes.
Values:
KR_NS_UPDATE
= = 0
-Update as smooth over last two measurements.
KR_NS_RESET
-Set to given value.
KR_NS_ADD
-Increment current value.
KR_NS_MAX
-Set to maximum of current/proposed value.
Functions
-
typedef
lru_t
(unsigned) NS reputation/QoS tracking.
-
KR_EXPORT int
kr_nsrep_set
(struct kr_query * qry, size_t index, const struct sockaddr * sock) Set given NS address.
- Return
- 0 or an error code
- Parameters
qry
-updated query
index
-index of the updated target
sock
-socket address to use (sockaddr_in or sockaddr_in6 or NULL)
-
KR_EXPORT int
kr_nsrep_elect
(struct kr_query * qry, struct kr_context * ctx) Elect best nameserver/address pair from the nsset.
- Return
- 0 or an error code
- Parameters
qry
-updated query
ctx
-resolution context
-
KR_EXPORT int
kr_nsrep_elect_addr
(struct kr_query * qry, struct kr_context * ctx) Elect best nameserver/address pair from the nsset.
- Return
- 0 or an error code
- Parameters
qry
-updated query
ctx
-resolution context
-
KR_EXPORT int
kr_nsrep_update_rtt
(struct kr_nsrep * ns, const struct sockaddr * addr, unsigned score, kr_nsrep_lru_t * cache, int umode) Update NS address RTT information.
In KR_NS_UPDATE mode reputation is smoothed over last N measurements.
- Return
- 0 on success, error code on failure
- Parameters
ns
-updated NS representation
addr
-chosen address (NULL for first)
score
-new score (i.e. RTT), see enum kr_ns_score
cache
-LRU cache
umode
-update mode (KR_NS_UPDATE or KR_NS_RESET or KR_NS_ADD)
-
KR_EXPORT int
kr_nsrep_update_rep
(struct kr_nsrep * ns, unsigned reputation, kr_nsrep_lru_t * cache) Update NSSET reputation information.
- Return
- 0 on success, error code on failure
- Parameters
ns
-updated NS representation
reputation
-combined reputation flags, see enum kr_ns_rep
cache
-LRU cache
-
struct
kr_nsrep
- #include <nsrep.h>
Name server representation.
Contains extra information about the name server, e.g. score or other metadata.
Public Members
-
unsigned
score
NS score.
-
unsigned
reputation
NS reputation.
-
const knot_dname_t *
name
NS name.
-
struct kr_context *
ctx
Resolution context.
-
union inaddr
addr
[KR_NSREP_MAXADDR] NS address(es)
-
unsigned
Functions
-
KR_EXPORT int
kr_zonecut_init
(struct kr_zonecut * cut, const knot_dname_t * name, knot_mm_t * pool) Populate root zone cut with SBELT.
- Return
- 0 or error code
- Parameters
cut
-zone cut
name
-pool
-
-
KR_EXPORT void
kr_zonecut_deinit
(struct kr_zonecut * cut) Clear the structure and free the address set.
- Parameters
cut
-zone cut
-
KR_EXPORT void
kr_zonecut_set
(struct kr_zonecut * cut, const knot_dname_t * name) Reset zone cut to given name and clear address list.
- Note
- This clears the address list even if the name doesn’t change. TA and DNSKEY don’t change.
- Parameters
cut
-zone cut to be set
name
-new zone cut name
-
KR_EXPORT int
kr_zonecut_copy
(struct kr_zonecut * dst, const struct kr_zonecut * src) Copy zone cut, including all data.
Does not copy keys and trust anchor.
- Return
- 0 or an error code
- Parameters
dst
-destination zone cut
src
-source zone cut
-
KR_EXPORT int
kr_zonecut_copy_trust
(struct kr_zonecut * dst, const struct kr_zonecut * src) Copy zone trust anchor and keys.
- Return
- 0 or an error code
- Parameters
dst
-destination zone cut
src
-source zone cut
-
KR_EXPORT int
kr_zonecut_add
(struct kr_zonecut * cut, const knot_dname_t * ns, const knot_rdata_t * rdata) Add address record to the zone cut.
The record will be merged with existing data, it may be either A/AAAA type.
- Return
- 0 or error code
- Parameters
cut
-zone cut to be populated
ns
-nameserver name
rdata
-nameserver address (as rdata)
-
KR_EXPORT int
kr_zonecut_del
(struct kr_zonecut * cut, const knot_dname_t * ns, const knot_rdata_t * rdata) Delete nameserver/address pair from the zone cut.
- Return
- 0 or error code
- Parameters
cut
-ns
-name server name
rdata
-name server address
-
KR_EXPORT int
kr_zonecut_del_all
(struct kr_zonecut * cut, const knot_dname_t * ns) Delete all addresses associated with the given name.
- Return
- 0 or error code
- Parameters
cut
-ns
-name server name
-
KR_EXPORT KR_PURE pack_t *
kr_zonecut_find
(struct kr_zonecut * cut, const knot_dname_t * ns) Find nameserver address list in the zone cut.
- Note
- This can be used for membership test, a non-null pack is returned if the nameserver name exists.
- Return
- pack of addresses or NULL
- Parameters
cut
-ns
-name server name
-
KR_EXPORT int
kr_zonecut_set_sbelt
(struct kr_context * ctx, struct kr_zonecut * cut) Populate zone cut with a root zone using SBELT :rfc:
1034
- Return
- 0 or error code
- Parameters
ctx
-resolution context (to fetch root hints)
cut
-zone cut to be populated
-
KR_EXPORT int
kr_zonecut_find_cached
(struct kr_context * ctx, struct kr_zonecut * cut, const knot_dname_t * name, uint32_t timestamp, bool *restrict secured) Populate zone cut address set from cache.
- Return
- 0 or error code (ENOENT if it doesn’t find anything)
- Parameters
ctx
-resolution context (to fetch data from LRU caches)
cut
-zone cut to be populated
name
-QNAME to start finding zone cut for
timestamp
-transaction timestamp
secured
-set to true if want secured zone cut, will return false if it is provably insecure
-
struct
kr_zonecut
- #include <zonecut.h>
Current zone cut representation.
Public Members
-
knot_dname_t *
name
Zone cut name.
-
knot_rrset_t *
key
Zone cut DNSKEY.
-
knot_rrset_t *
trust_anchor
Current trust anchor.
-
struct kr_zonecut *
parent
Parent zone cut.
-
map_t
nsset
Map of nameserver => address_set.
-
knot_mm_t *
pool
Memory pool.
-
knot_dname_t *
Modules¶
Module API definition and functions for (un)loading modules.
Defines
- KR_MODULE_EXPORT(module)
Export module API version (place this at the end of your module).
- Parameters
module
-module name (f.e. hints)
- KR_MODULE_API
Typedefs
-
typedef uint32_t(
module_api_cb
)(void)
-
typedef char *(
kr_prop_cb
)(void *env, struct kr_module *self, const char *input) Module property callback.
Input and output is passed via a JSON encoded in a string.
- Return
- a free-form JSON output (malloc-ated)
- Parameters
env
-pointer to the lua engine, i.e. struct engine *env (TODO: explicit type)
input
-parameter (NULL if missing/nil on lua level)
Functions
-
KR_EXPORT int
kr_module_load
(struct kr_module * module, const char * name, const char * path) Load a C module instance into memory.
- Return
- 0 or an error
- Parameters
module
-module structure
name
-module name
path
-module search path
-
KR_EXPORT void
kr_module_unload
(struct kr_module * module) Unload module instance.
- Parameters
module
-module structure
-
struct
kr_module
- #include <module.h>
Module representation.
The five symbols (init, ...) may be defined by the module as name_init(), etc; all are optional and missing symbols are represented as NULLs;
Public Members
-
char *
name
-
int(*
init
)(struct kr_module *self) Constructor.
Called after loading the module.
- Return
- error code.
-
int(*
deinit
)(struct kr_module *self) Destructor.
Called before unloading the module.
- Return
- error code.
-
int(*
config
)(struct kr_module *self, const char *input) Configure with encoded JSON (NULL if missing).
- Return
- error code.
-
const kr_layer_api_t *(*
layer
)(struct kr_module *self) Get a pointer to packet processing API specs.
See docs on that type.
-
const struct kr_prop *(*
props
)(void) Get a pointer to list of properties, terminated by { NULL, NULL, NULL }.
-
void *
lib
Shared library handle or RTLD_DEFAULT.
-
void *
data
Custom data context.
-
char *
-
struct
kr_prop
- #include <module.h>
Module property (named callable).
Utilities¶
Defines
- kr_log_info(fmt, ...)
- kr_log_error(fmt, ...)
- WITH_VERBOSE
Block run in verbose mode; optimized when not run.
- kr_log_verbose
- static_assert(cond, msg)
- RDATA_ARR_MAX
- kr_rdataset_next(rd)
- KR_RRKEY_LEN
- SWAP(x, y)
Swap two places.
Note: the parameters need to be without side effects.
Functions
-
KR_EXPORT bool
kr_verbose_set
(bool status) Set verbose mode.
Not available if compiled with -DNOVERBOSELOG.
-
KR_EXPORT void
kr_log_verbose
(const char * fmt, ...) Log a message if in verbose mode.
-
long
time_diff
(struct timeval * begin, struct timeval * end) Return time difference in miliseconds.
- Note
- based on the _BSD_SOURCE timersub() macro
-
KR_EXPORT char *
kr_strcatdup
(unsigned n, ...) Concatenate N strings.
-
int
kr_rand_reseed
(void) Reseed CSPRNG context.
-
KR_EXPORT uint32_t
kr_rand_uint
(uint32_t max) Get pseudo-random value between zero and max-1 (inclusive).
Passing zero means that any uint32_t should be returned (it’s also faster).
-
KR_EXPORT int
kr_memreserve
(void * baton, char ** mem, size_t elm_size, size_t want, size_t * have) Memory reservation routine for knot_mm_t.
-
KR_EXPORT int
kr_pkt_recycle
(knot_pkt_t * pkt)
-
KR_EXPORT int
kr_pkt_clear_payload
(knot_pkt_t * pkt)
-
KR_EXPORT int
kr_pkt_put
(knot_pkt_t * pkt, const knot_dname_t * name, uint32_t ttl, uint16_t rclass, uint16_t rtype, const uint8_t * rdata, uint16_t rdlen) Construct and put record to packet.
-
KR_EXPORT void
kr_pkt_make_auth_header
(knot_pkt_t * pkt) Set packet header suitable for authoritative answer.
(for policy module)
-
KR_EXPORT KR_PURE const char *
kr_inaddr
(const struct sockaddr * addr) Address bytes for given family.
-
KR_EXPORT KR_PURE int
kr_inaddr_family
(const struct sockaddr * addr) Address family.
-
KR_EXPORT KR_PURE int
kr_inaddr_len
(const struct sockaddr * addr) Address length for given family.
-
KR_EXPORT KR_PURE uint16_t
kr_inaddr_port
(const struct sockaddr * addr) Port.
-
KR_EXPORT KR_PURE int
kr_straddr_family
(const char * addr) Return address type for string.
-
KR_EXPORT KR_CONST int
kr_family_len
(int family) Return address length in given family.
-
KR_EXPORT struct sockaddr *
kr_straddr_socket
(const char * addr, int port) Create a sockaddr* from string+port representation (also accepts IPv6 link-local).
-
KR_EXPORT int
kr_straddr_subnet
(void * dst, const char * addr) Parse address and return subnet length (bits).
- Warning
- ‘dst’ must be at least
sizeof(struct in6_addr)
long.
-
KR_EXPORT KR_PURE int
kr_bitcmp
(const char * a, const char * b, int bits) Compare memory bitwise.
The semantics is “the same” as for memcmp(). The partial byte is considered with more-significant bits first, so this is e.g. suitable for comparing IP prefixes.
-
uint8_t
KEY_FLAG_RANK
(const char * key)
-
bool
KEY_COVERING_RRSIG
(const char * key)
-
KR_EXPORT int
kr_rrkey
(char * key, const knot_dname_t * owner, uint16_t type, uint8_t rank) Create unique null-terminated string key for RR.
- Return
- key length if successful or an error
- Parameters
key
-Destination buffer for key size, MUST be KR_RRKEY_LEN or larger.
owner
-RR owner domain name.
type
-RR type.
rank
-RR rank (8 bit tag usable for anything).
-
int
kr_rrmap_add
(map_t * stash, const knot_rrset_t * rr, uint8_t rank, knot_mm_t * pool)
-
KR_EXPORT int
kr_ranked_rrarray_add
(ranked_rr_array_t * array, const knot_rrset_t * rr, uint8_t rank, bool to_wire, uint32_t qry_uid, knot_mm_t * pool)
-
int
kr_ranked_rrarray_set_wire
(ranked_rr_array_t * array, bool to_wire, uint32_t qry_uid, bool check_dups, bool(*)(const ranked_rr_array_entry_t *) extraCheck)
-
void
kr_rrset_print
(const knot_rrset_t * rr, const char * prefix)
-
void
kr_qry_print
(const struct kr_query * qry, const char * prefix, const char * postfix)
-
void
kr_pkt_print
(knot_pkt_t * pkt)
-
void
kr_dname_print
(const knot_dname_t * name, const char * prefix, const char * postfix)
-
void
kr_rrtype_print
(const uint16_t rrtype, const char * prefix, const char * postfix)
-
KR_EXPORT char *
kr_module_call
(struct kr_context * ctx, const char * module, const char * prop, const char * input) Call module property.
-
uint16_t
kr_rrset_type_maysig
(const knot_rrset_t * rr) Return the (covered) type of an nonempty RRset.
-
const char *
lua_push_printf
(lua_State * L, const char * fmt, ...) Printf onto the lua stack, avoiding additional copy (thin wrapper).
-
KR_EXPORT uint64_t
kr_now
() The current time in monotonic milliseconds.
- Note
- it may be outdated in case of long callbacks; see uv_now().
Variables
-
KR_EXPORT bool
kr_verbose_status
Whether in verbose mode.
Only use this for reading.
-
const uint8_t
KEY_FLAG_RRSIG
-
union
inaddr
- #include <utils.h>
Simple storage for IPx address or AF_UNSPEC.
Public Members
-
struct sockaddr
ip
-
struct sockaddr_in
ip4
-
struct sockaddr_in6
ip6
-
struct sockaddr
Defines
- KR_EXPORT
- KR_CONST
- KR_PURE
- KR_NORETURN
- KR_COLD
- uint
- kr_ok()
- kr_strerror(x)
Typedefs
-
typedef unsigned int
uint
Functions
-
int KR_COLD
kr_error
(int x)
Generics library¶
This small collection of “generics” was born out of frustration that I couldn’t find no such thing for C. It’s either bloated, has poor interface, null-checking is absent or doesn’t allow custom allocation scheme. BSD-licensed (or compatible) code is allowed here, as long as it comes with a test case in tests/test_generics.c.
- array - a set of simple macros to make working with dynamic arrays easier.
- map - a Crit-bit tree key-value map implementation (public domain) that comes with tests.
- set - set abstraction implemented on top of
map
. - pack - length-prefixed list of objects (i.e. array-list).
- lru - LRU-like hash table
array¶
A set of simple macros to make working with dynamic arrays easier.
MIN(array_push(arr, val), other)
- Note
- The C has no generics, so it is implemented mostly using macros. Be aware of that, as direct usage of the macros in the evaluating macros may lead to different expectations:
May evaluate the code twice, leading to unexpected behaviour. This is a price to pay for the absence of proper generics.
Example usage:
array_t(const char*) arr;
array_init(arr);
// Reserve memory in advance
if (array_reserve(arr, 2) < 0) {
return ENOMEM;
}
// Already reserved, cannot fail
array_push(arr, "princess");
array_push(arr, "leia");
// Not reserved, may fail
if (array_push(arr, "han") < 0) {
return ENOMEM;
}
// It does not hide what it really is
for (size_t i = 0; i < arr.len; ++i) {
printf("%s\n", arr.at[i]);
}
// Random delete
array_del(arr, 0);
Defines
- array_t(type)
Declare an array structure.
- array_init(array)
Zero-initialize the array.
- array_clear(array)
Free and zero-initialize the array.
- array_clear_mm(array, free, baton)
- array_reserve(array, n)
Reserve capacity up to ‘n’ bytes.
- Return
- 0 if success, <0 on failure
- array_reserve_mm(array, n, reserve, baton)
- array_push(array, val)
Push value at the end of the array, resize it if necessary.
- Note
- May fail if the capacity is not reserved.
- Return
- element index on success, <0 on failure
- array_pop(array)
Pop value from the end of the array.
- array_del(array, i)
Remove value at given index.
- Return
- 0 on success, <0 on failure
- array_tail(array)
Return last element of the array.
- Warning
- Undefined if the array is empty.
Functions
-
size_t
array_next_count
(size_t want) Simplified Qt containers growth strategy.
-
int
array_std_reserve
(void * baton, char ** mem, size_t elm_size, size_t want, size_t * have)
-
void
array_std_free
(void * baton, void * p)
map¶
A Crit-bit tree key-value map implementation.
Example usage:
- Warning
- If the user provides a custom allocator, it must return addresses aligned to 2B boundary.
map_t map = map_make();
// Custom allocator (optional)
map.malloc = &mymalloc;
map.baton = &mymalloc_context;
// Insert k-v pairs
int values = { 42, 53, 64 };
if (map_set(&map, "princess", &values[0]) != 0 ||
map_set(&map, "prince", &values[1]) != 0 ||
map_set(&map, "leia", &values[2]) != 0) {
fail();
}
// Test membership
if (map_contains(&map, "leia")) {
success();
}
// Prefix search
int i = 0;
int count(const char *k, void *v, void *ext) { (*(int *)ext)++; return 0; }
if (map_walk_prefixed(map, "princ", count, &i) == 0) {
printf("%d matches\n", i);
}
// Delete
if (map_del(&map, "badkey") != 0) {
fail(); // No such key
}
// Clear the map
map_clear(&map);
Defines
- map_walk(map, callback, baton)
Typedefs
-
typedef void *(*
map_alloc_f
)(void *, size_t)
-
typedef void(*
map_free_f
)(void *baton, void *ptr)
Functions
-
map_t
map_make
(void) Creates an new, empty critbit map.
-
int
map_contains
(map_t * map, const char * str) Returns non-zero if map contains str.
-
void *
map_get
(map_t * map, const char * str) Returns value if map contains str.
-
int
map_set
(map_t * map, const char * str, void * val) Inserts str into map, returns 0 on suceess.
-
int
map_del
(map_t * map, const char * str) Deletes str from the map, returns 0 on suceess.
-
void
map_clear
(map_t * map) Clears the given map.
-
int
map_walk_prefixed
(map_t * map, const char * prefix, int(*)(const char *, void *, void *) callback, void * baton) Calls callback for all strings in map with the given prefix.
- Parameters
map
-prefix
-required string prefix (empty => all strings)
callback
-callback parameters are (key, value, baton)
baton
-passed uservalue
-
struct
map_t
- #include <map.h>
Main data structure.
Public Members
-
void *
root
-
map_alloc_f
malloc
-
map_free_f
free
-
void *
baton
-
void *
set¶
A set abstraction implemented on top of map.
Example usage:
- Note
- The API is based on map.h, see it for more examples.
set_t set = set_make();
// Insert keys
if (set_add(&set, "princess") != 0 ||
set_add(&set, "prince") != 0 ||
set_add(&set, "leia") != 0) {
fail();
}
// Test membership
if (set_contains(&set, "leia")) {
success();
}
// Prefix search
int i = 0;
int count(const char *s, void *n) { (*(int *)n)++; return 0; }
if (set_walk_prefixed(set, "princ", count, &i) == 0) {
printf("%d matches\n", i);
}
// Delete
if (set_del(&set, "badkey") != 0) {
fail(); // No such key
}
// Clear the set
set_clear(&set);
Defines
- set_make()
Creates an new, empty critbit set
- set_contains(set, str)
Returns non-zero if set contains str
- set_add(set, str)
Inserts str into set, returns 0 on suceess
- set_del(set, str)
Deletes str from the set, returns 0 on suceess
- set_clear(set)
Clears the given set
- set_walk(set, callback, baton)
Calls callback for all strings in map
- set_walk_prefixed(set, prefix, callback, baton)
Calls callback for all strings in set with the given prefix
pack¶
A length-prefixed list of objects, also an array list.
Each object is prefixed by item length, unlike array this structure permits variable-length data. It is also equivallent to forward-only list backed by an array.
Example usage:
- Note
- Maximum object size is 2^16 bytes, see pack_objlen_t If some mistake happens somewhere, the access may end up in an infinite loop. (equality comparison on pointers)
pack_t pack;
pack_init(pack);
// Reserve 2 objects, 6 bytes total
pack_reserve(pack, 2, 4 + 2);
// Push 2 objects
pack_obj_push(pack, U8("jedi"), 4)
pack_obj_push(pack, U8("\xbe\xef"), 2);
// Iterate length-value pairs
uint8_t *it = pack_head(pack);
while (it != pack_tail(pack)) {
uint8_t *val = pack_obj_val(it);
it = pack_obj_next(it);
}
// Remove object
pack_obj_del(pack, U8("jedi"), 4);
pack_clear(pack);
Defines
- pack_init(pack)
Zero-initialize the pack.
- pack_clear(pack)
Free and the pack.
- pack_clear_mm(pack, free, baton)
- pack_reserve(pack, objs_count, objs_len)
Incrementally reserve objects in the pack.
- pack_reserve_mm(pack, objs_count, objs_len, reserve, baton)
- pack_head(pack)
Return pointer to first packed object.
- pack_tail(pack)
Return pack end pointer.
Typedefs
-
typedef uint16_t
pack_objlen_t
Packed object length type.
Functions
-
typedef
array_t
(uint8_t) Pack is defined as an array of bytes.
-
pack_objlen_t
pack_obj_len
(uint8_t * it) Return packed object length.
-
uint8_t *
pack_obj_val
(uint8_t * it) Return packed object value.
-
uint8_t *
pack_obj_next
(uint8_t * it) Return pointer to next packed object.
-
uint8_t *
pack_last
(pack_t pack) Return pointer to the last packed object.
-
int
pack_obj_push
(pack_t * pack, const uint8_t * obj, pack_objlen_t len) Push object to the end of the pack.
- Return
- 0 on success, negative number on failure
-
uint8_t *
pack_obj_find
(pack_t * pack, const uint8_t * obj, pack_objlen_t len) Returns a pointer to packed object.
- Return
- pointer to packed object or NULL
-
int
pack_obj_del
(pack_t * pack, const uint8_t * obj, pack_objlen_t len) Delete object from the pack.
- Return
- 0 on success, negative number on failure
lru¶
A lossy cache.
Example usage:
- Note
- The implementation tries to keep frequent keys and avoid others, even if “used recently”, so it may refuse to store it on lru_get_new(). It uses hashing to split the problem pseudo-randomly into smaller groups, and within each it tries to approximate relative usage counts of several most frequent keys/hashes. This tracking is done for more keys than those that are actually stored.
// Define new LRU type
typedef lru_t(int) lru_int_t;
// Create LRU
lru_int_t *lru;
lru_create(&lru, 5, NULL);
// Insert some values
int *pi = lru_get_new(lru, "luke", strlen("luke"));
if (pi)
*pi = 42;
pi = lru_get_new(lru, "leia", strlen("leia"));
if (pi)
*pi = 24;
// Retrieve values
int *ret = lru_get_try(lru, "luke", strlen("luke"));
if (!ret) printf("luke dropped out!\n");
else printf("luke's number is %d\n", *ret);
char *enemies[] = {"goro", "raiden", "subzero", "scorpion"};
for (int i = 0; i < 4; ++i) {
int *val = lru_get_new(lru, enemies[i], strlen(enemies[i]));
if (val)
*val = i;
}
// We're done
lru_free(lru);
Defines
- lru_t(type)
The type for LRU, parametrized by value type.
- lru_create(ptable, max_slots, mm_ctx_array, mm_ctx)
Allocate and initialize an LRU with default associativity.
The real limit on the number of slots can be a bit larger but less than double.
- Note
- The pointers to memory contexts need to remain valid during the whole life of the structure (or be NULL).
- Parameters
ptable
-pointer to a pointer to the LRU
max_slots
-number of slots
mm_ctx_array
-memory context to use for the huge array, NULL for default
mm_ctx
-memory context to use for individual key-value pairs, NULL for default
- lru_free(table)
Free an LRU created by lru_create (it can be NULL).
- lru_reset(table)
Reset an LRU to the empty state (but preserve any settings).
- lru_get_try(table, key_, len_)
Find key in the LRU and return pointer to the corresponding value.
- Return
- pointer to data or NULL if not found
- Parameters
table
-pointer to LRU
key_
-lookup key
len_
-key length
- lru_get_new(table, key_, len_)
Return pointer to value, inserting if needed (zeroed).
- Return
- pointer to data or NULL (can be even if memory could be allocated!)
- Parameters
table
-pointer to LRU
key_
-lookup key
len_
-key lengthkeys
- lru_apply(table, function, baton)
Apply a function to every item in LRU.
- Parameters
table
-pointer to LRU
function
-enum lru_apply_do (*function)(const char *key, uint len, val_type *val, void *baton) See enum lru_apply_do for the return type meanings.
baton
-extra pointer passed to each function invocation
- lru_capacity(table)
Return the real capacity - maximum number of keys holdable within.
- Parameters
table
-pointer to LRU
Enums
- lru_apply_do enum
Possible actions to do with an element.
Values:
LRU_APPLY_DO_NOTHING
-LRU_APPLY_DO_EVICT
-
Functions
-
uint
round_power
(uint size, uint power) Round the value up to a multiple of (1 << power).