id.c

Go to the documentation of this file.

/*
 *   This library is free software; you can redistribute it and/or
 *   modify it under the terms of the GNU Lesser General Public
 *   License as published by the Free Software Foundation; either
 *   version 2.1 of the License, or (at your option) any later version.
 *
 *   This library 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
 *   Lesser General Public License for more details.
 *
 *   You should have received a copy of the GNU Lesser General Public
 *   License along with this library; if not, write to the Free Software
 *   Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301, USA
 */
 
/**
 * $Id: 170d9d103bbae2f33781296e65eac7197f07f076 $
 *
 * @file protocols/radius/id.c
 * @brief Functions to allocate 8-bit IDs for a particular socket.
 *
 * @copyright 2024 Network RADIUS SAS (legal@networkradius.com)
 */
RCSID("$Id: 170d9d103bbae2f33781296e65eac7197f07f076 $")
 
#include <freeradius-devel/radius/id.h>
 
struct fr_radius_id_s {
        int                     num_free_ids;   //!< number of used IDs
 
        int                     free_start;
        int                     free_end;
 
        fr_radius_id_ctx_t      id[256];        //!< pointers to request / reply data
 
        int                     free_ids[256];
};
 
 
 
/** Allocate a tracking structure for one packet code.
 *
 */
fr_radius_id_t *fr_radius_id_alloc(TALLOC_CTX *ctx)
{
        uint32_t i;
        fr_radius_id_t *track;
 
        track = talloc_zero(ctx, fr_radius_id_t);
        if (!track) return NULL;
 
        track->num_free_ids = 256;
        track->free_start = 0;
        track->free_end = 0;
 
        for (i = 0; i < 256; i++) {
                track->free_ids[i] = i;
        }
 
        /*
         *      Shuffle the entirs using a Fisher-Yates shuffle.
         *
         *      We loop from i=255..1, choosing random numbers j, such that 0 <= j <= i
         *      And then swap a[j],a[i]
         *
         *      We choose a 32-bit random number, and then take the modulo of that and i+1.  Which means that
         *      the resulting random number j is [0..i], whereas taking the modulo with i, then the random
         *      number j will instead be chosen to be [0..i)
         */
        for (i = 255; i >= 1; i--) {
                uint32_t j = fr_rand() % (i + 1); /* small bias, but we don't care much */
                int tmp;
 
                if (j == i) continue;
 
                tmp = track->free_ids[j];
                track->free_ids[j] = track->free_ids[i];
                track->free_ids[i] = tmp;
        }
 
 
        return track;
}
 
/** Allocate an ID for a packet, using LRU
 *
 */
fr_radius_id_ctx_t *fr_radius_id_pop(fr_radius_id_t *track, fr_packet_t *packet)
{
        int id;
 
        id = track->free_ids[track->free_start];
        fr_assert(id >= 0);
        fr_assert(id < 256);
 
        fr_assert(!track->id[id].packet);
 
        track->free_ids[track->free_start] = -1;
 
        track->free_start++;
        track->free_start &= 0xff;
 
        fr_assert(track->num_free_ids > 0);
        track->num_free_ids--;
 
        track->id[id] = (fr_radius_id_ctx_t) {
                .packet = packet,
        };
        packet->id = id;
 
        return &track->id[id];
}
 
/** De-allocate an ID for a packet, using LRU
 *
 */
void fr_radius_id_push(fr_radius_id_t *track, fr_packet_t const *packet)
{
        fr_assert(packet->id >= 0);
        fr_assert(packet->id < 256);
 
        fr_assert(track->id[packet->id].packet == packet);
        fr_assert(track->num_free_ids < 256);
        fr_assert(track->free_start != track->free_end);
        fr_assert(track->free_end >= 0);
        fr_assert(track->free_end < 256);
        fr_assert(track->free_ids[track->free_end] == -1);
 
        track->free_ids[track->free_end] = packet->id;
 
        track->free_end++;
        track->free_end &= 0xff;
 
        track->id[packet->id].packet = NULL;
        track->num_free_ids++;
}
 
fr_radius_id_ctx_t *fr_radius_id_find(fr_radius_id_t *track, int id)
{
        fr_assert(id >= 0);
        fr_assert(id < 256);
 
        return &track->id[id];
}
 
/**  Forces the next ID to be the given one
 *
 */
int fr_radius_id_force(fr_radius_id_t *track, int id)
{
        int i, first;
 
        fr_assert(id >= 0);
        fr_assert(id < 256);
 
        for (i = 0; i < 256; i++) {
                if (track->free_ids[(track->free_start + i) & 0xff] != id) continue;
 
                /*
                 *      It's already the first one.  We don't need to do any more.
                 */
                if (i == 0) return 0;
 
                first = track->free_ids[track->free_start];
                track->free_ids[track->free_start] = id;
                track->free_ids[(track->free_start + i) & 0xff] = first;
 
                return 0;
        }
 
        fr_strerror_const("Cannot assign ID");
        return -1;
}