summaryrefslogtreecommitdiff
path: root/mac/ca
diff options
context:
space:
mode:
Diffstat (limited to 'mac/ca')
-rw-r--r--mac/ca/Module2
-rw-r--r--mac/ca/ca.h72
-rw-r--r--mac/ca/inc/alloc.h58
-rw-r--r--mac/ca/inc/backoff.h10
-rw-r--r--mac/ca/inc/context.h23
-rw-r--r--mac/ca/mfs.h26
-rw-r--r--mac/ca/src/access.c218
-rw-r--r--mac/ca/src/alloc.c123
-rw-r--r--mac/ca/src/backoff.c9
-rw-r--r--mac/ca/src/ca.c97
-rw-r--r--mac/ca/test/backoff/Makefile7
-rw-r--r--mac/ca/test/ca/Makefile7
-rw-r--r--mac/ca/test/ca/inc/phy_stub.h23
-rw-r--r--mac/ca/test/ca/src/phy_stub.c55
-rw-r--r--mac/ca/test/ca/src/test_alloc.c186
-rw-r--r--mac/ca/test/ca/src/test_backoff.c (renamed from mac/ca/test/backoff/src/test_backoff.c)29
-rw-r--r--mac/ca/test/ca/src/test_ca.c32
17 files changed, 926 insertions, 51 deletions
diff --git a/mac/ca/Module b/mac/ca/Module
index 6f402ca462..30ee2dccb2 100644
--- a/mac/ca/Module
+++ b/mac/ca/Module
@@ -1 +1 @@
-SOURCES := backoff.c
+SOURCES := access.c alloc.c backoff.c ca.c
diff --git a/mac/ca/ca.h b/mac/ca/ca.h
index 77338f304d..37e216beab 100644
--- a/mac/ca/ca.h
+++ b/mac/ca/ca.h
@@ -13,6 +13,9 @@
* \ingroup mac_ca
*/
#include "mac/common/mfs.h"
+#include "hal/phy/forward.h"
+#include "mac/common/config.h"
+#include "mac/common/store.h"
/* Forward declaration. */
typedef struct ca_t ca_t;
@@ -25,8 +28,11 @@ typedef struct ca_t ca_t;
* - the schedule for the future beacon period using the current persistent
* schedule for which we have no non-persistent schedule;
* - the persistent preview schedule, also without non-persistent schedule.
+ *
+ * Moreover, to update the schedules without altering the used ones, the upper
+ * layer may need four other schedules.
*/
-#define CA_SCHEDULE_NB 4
+#define CA_SCHEDULE_NB 8
/** Schedule maximum size.
* One transmitted schedule can have a maximum of 64 allocation entries, but
@@ -42,7 +48,8 @@ typedef struct ca_t ca_t;
/** Beacon period circular buffer size.
* Current schedule can be valid for 8 beacon periods. Preview schedule can
- * be valid after 7 period. */
+ * be valid after 7 period. An additional slot is required for the circular
+ * buffer function. */
#define CA_BEACON_PERIOD_NB 16
/** Beacon period entry. */
@@ -59,7 +66,7 @@ typedef struct ca_beacon_period_t ca_beacon_period_t;
struct ca_allocation_t
{
/** Allocation end date as an offset from the beacon period start. */
- u32 end_date:24;
+ u32 end_offset_tck:24;
/** GLID of this allocation.
* - 0xff: local CSMA allocation,
* - 0xfe: shared CSMA allocation,
@@ -74,7 +81,8 @@ typedef struct ca_allocation_t ca_allocation_t;
/** Channel Access schedule.
* It should contains allocations from the persistent schedule, the
- * non-persistent schedule and also entries for holes. */
+ * non-persistent schedule and also entries for holes. Consecutive shared
+ * CSMA allocations should be merged in one allocation by the upper layer. */
struct ca_schedule_t
{
/** Number of used allocations in this schedule. */
@@ -89,11 +97,16 @@ typedef struct ca_schedule_t ca_schedule_t;
struct ca_access_param_t
{
/** Scheduled MFS. */
- mfs_t *mfs;
+ mfs_tx_t *mfs;
+ /** Programmed ACCESS date. Does not include anticipation, but does
+ * include backoff. */
+ u32 access_date;
/** Available time. */
uint duration_tck;
- /** Did we play the contention game. */
- bool did_content;
+ /** Does it occurs during a contention free period? */
+ bool cfp:1;
+ /** Should it content for ACCESS? */
+ bool content:1;
};
typedef struct ca_access_param_t ca_access_param_t;
@@ -101,10 +114,11 @@ BEGIN_DECLS
/**
* Initialise ca and return its context.
+ * \param phy phy context
* \return ca context
*/
ca_t *
-ca_init (void);
+ca_init (phy_t *phy, mac_config_t *config, mac_store_t *store);
/**
* Uninitialise a ca context.
@@ -116,7 +130,7 @@ ca_uninit (ca_t *ctx);
/**
* Restart VCS.
* \param ctx ca context
- * \param date start date
+ * \param start_date VCS start date
* \param length_tck VCS length
* \param anticipation_tck ACCESS event anticipation
* \param eifs true if this is an EIFS
@@ -131,8 +145,8 @@ ca_uninit (ca_t *ctx);
* allocation.
*/
void
-ca_vcs_restart (ca_t *ctx, u32 date, uint length_tck, uint anticipation_tck,
- bool eifs);
+ca_access_vcs_restart (ca_t *ctx, u32 start_date, uint length_tck,
+ uint anticipation_tck, bool eifs);
/**
* Program hardware ACCESS timer.
@@ -144,13 +158,13 @@ ca_vcs_restart (ca_t *ctx, u32 date, uint length_tck, uint anticipation_tck,
* responses or bursts where we know we have the medium access.
*/
void
-ca_vcs_access (ca_t *ctx, u32 date, uint anticipation_tck);
+ca_access_program (ca_t *ctx, u32 date, uint anticipation_tck);
/**
* Update next ACCESS information for the given grant.
* \param ctx ca context
- * \param duration_tck grant duration
* \param mfs granted MFS or NULL for any MFS
+ * \param duration_tck grant duration
*
* Grants are given by CCo with RTS/CTS with immediate grant flag set, or by
* bidirectional bursts.
@@ -159,7 +173,7 @@ ca_vcs_access (ca_t *ctx, u32 date, uint anticipation_tck);
* information delivered when an ACCESS event occurs.
*/
void
-ca_grant (ca_t *ctx, uint duration_tck, mfs_t *mfs);
+ca_access_grant (ca_t *ctx, mfs_tx_t *mfs, uint duration_tck);
/**
* Get ACCESS parameters.
@@ -169,7 +183,7 @@ ca_grant (ca_t *ctx, uint duration_tck, mfs_t *mfs);
* This structure is valid just after the ACCESS event.
*/
const ca_access_param_t *
-ca_get_access_param (ca_t *ctx);
+ca_access_get_param (ca_t *ctx);
/**
* Update backoff after a deferral.
@@ -200,6 +214,24 @@ void
ca_backoff_success (ca_t *ctx);
/**
+ * Initialise Channel Access related parameters in an MFS TX.
+ * \param mfs the newly created MFS
+ *
+ * The MFS is not registered in the Channel Access queues.
+ */
+void
+ca_mfs_init (ca_t *ctx, mfs_tx_t *mfs);
+
+/**
+ * Uninitialise Channel Access related parameters in an MFS TX prior to
+ * deletion.
+ * \param ctx ca context
+ * \param mfs the MFS to be deleted
+ */
+void
+ca_mfs_uninit (ca_t *ctx, mfs_tx_t *mfs);
+
+/**
* Update Channel Access after a MFS update.
* \param ctx ca context
* \param mfs the updated MFS
@@ -209,7 +241,7 @@ ca_backoff_success (ca_t *ctx);
* chosen for the next transmission.
*/
void
-ca_mfs_update (ca_t *ctx, mfs_t *mfs);
+ca_mfs_update (ca_t *ctx, mfs_tx_t *mfs);
/**
* Retrieve a pointer to a schedule table entry.
@@ -220,7 +252,7 @@ ca_mfs_update (ca_t *ctx, mfs_t *mfs);
* This should only be done if the schedule is not currently used.
*/
ca_schedule_t *
-ca_schedule_get (ca_t *ctx, uint index);
+ca_alloc_get_schedule (ca_t *ctx, uint index);
/**
* Update the beacon periods.
@@ -233,9 +265,9 @@ ca_schedule_get (ca_t *ctx, uint index);
* could trigger an extra computation of the next access.
*/
void
-ca_beacon_periods_update (ca_t *ctx,
- ca_beacon_period_t *beacon_periods,
- uint beacon_periods_nb);
+ca_alloc_update_beacon_periods (ca_t *ctx,
+ ca_beacon_period_t *beacon_periods,
+ uint beacon_periods_nb);
END_DECLS
diff --git a/mac/ca/inc/alloc.h b/mac/ca/inc/alloc.h
new file mode 100644
index 0000000000..d5688cf34d
--- /dev/null
+++ b/mac/ca/inc/alloc.h
@@ -0,0 +1,58 @@
+#ifndef mac_ca_inc_alloc_h
+#define mac_ca_inc_alloc_h
+/* Cesar project {{{
+ *
+ * Copyright (C) 2007 Spidcom
+ *
+ * <<<Licence>>>
+ *
+ * }}} */
+/**
+ * \file mac/ca/inc/alloc.h
+ * \brief Beacon period and schedule related functions header.
+ * \ingroup mac_ca
+ */
+
+/** Get the next beacon period index in the circular buffer. */
+#define CA_ALLOC_NEXT_BEACON_PERIOD(x) (((x) + 1) % CA_BEACON_PERIOD_NB)
+
+/** Is the specified LID a CSMA one. Theses are the LID used in beacon
+ * entries. */
+#define CA_ALLOC_IS_CSMA(lid) ((lid) == MAC_LID_SHARED_CSMA \
+ || (lid) == MAC_LID_LOCAL_CSMA)
+
+/** Should transmissions in the specified allocation use hybrid frame
+ * controls according to the specified coexistence mode. */
+#define CA_ALLOC_IS_HYBRID(coex, lid) \
+ (lid == MAC_LID_DISCOVER \
+ || ((lid) == MAC_LID_SHARED_CSMA \
+ && coex != MAC_COEXISTENCE_AV_ONLY_MODE) \
+ || coex == MAC_COEXISTENCE_FULL_HYBRID_MODE \
+ || coex == MAC_COEXISTENCE_HYBRID_DELIMITERS_MODE)
+
+/**
+ * Find the beacon period index corresponding to the given date.
+ * \param ctx ca context
+ * \param date date to search
+ * \return index in the beacon periods circular buffer or buffer tail if no
+ * beacon period corresponding (no beacon period at all or first beacon period
+ * after the given date)
+ *
+ * Dates have more chance to be at the begin of the circular buffer, in the
+ * current beacon period. Start search at the buffer begin.
+ */
+uint
+ca_alloc_find_beacon_period (const ca_t *ctx, u32 date);
+
+/**
+ * Find the allocation corresponding to the given date offset.
+ * \param sched schedule
+ * \param offset_tck offset to search
+ * \return allocation index, or allocations_nb if not found
+ *
+ * Use dichotomy, no prior assumption about dates repartition.
+ */
+uint
+ca_alloc_find (const ca_schedule_t *sched, uint offset_tck);
+
+#endif /* mac_ca_inc_alloc_h */
diff --git a/mac/ca/inc/backoff.h b/mac/ca/inc/backoff.h
index c22cea39e6..30f90899ba 100644
--- a/mac/ca/inc/backoff.h
+++ b/mac/ca/inc/backoff.h
@@ -51,6 +51,16 @@ ca_backoff_init (ca_t *ctx);
void
ca_backoff_new (ca_t *ctx, uint cap);
+/**
+ * Cancel a backoff initialisation.
+ * \param ctx ca context
+ *
+ * Called when ca_backoff_new() has been called and the backoff parameters
+ * were finally not used.
+ */
+void
+ca_backoff_cancel (ca_t *ctx);
+
/* ca_backoff_deferred is public */
/* ca_backoff_success is public */
diff --git a/mac/ca/inc/context.h b/mac/ca/inc/context.h
index a435028537..9eac1fa0d6 100644
--- a/mac/ca/inc/context.h
+++ b/mac/ca/inc/context.h
@@ -13,6 +13,8 @@
* \ingroup mac_ca
*/
+#include "lib/heap.h"
+
#include "mac/ca/ca.h"
#include "mac/common/mfs.h"
@@ -21,15 +23,20 @@
/** Channel Access context. */
struct ca_t
{
+ /** Phy context. */
+ phy_t *phy;
+ /** Global configuration. */
+ mac_config_t *config;
+ /** MAC STA & MFS store. */
+ mac_store_t *store;
/** Next ACCESS event parameters. */
ca_access_param_t access_param;
- /** End date of the current VCS. */
- u32 vcs_end_date;
- /** Programmed end date. It may be further than vcs_end_date when
- * it lands in a unusable region or sooner when we have a exclusive
- * access to the medium for a response or a burst. Does not include
- * anticipation. */
- u32 programmed_end_date;
+ /** Start date of the current VCS. */
+ u32 vcs_start_date;
+ /** Length of the current VCS. */
+ uint vcs_length_tck;
+ /** Is current VCS a EIFS. */
+ bool vcs_eifs;
/** Programmed anticipation, may be needed if the timer must be
* reprogrammed. */
u32 anticipation_tck;
@@ -41,6 +48,8 @@ struct ca_t
ca_beacon_period_t beacon_periods[CA_BEACON_PERIOD_NB];
/** Schedules table. */
ca_schedule_t schedules[CA_SCHEDULE_NB];
+ /** Priority sorted MFS heap. */
+ heap_t mfs_heap;
};
/* Forward declaration in mac/ca/ca.h. */
diff --git a/mac/ca/mfs.h b/mac/ca/mfs.h
new file mode 100644
index 0000000000..e86a002a1b
--- /dev/null
+++ b/mac/ca/mfs.h
@@ -0,0 +1,26 @@
+#ifndef mac_ca_mfs_h
+#define mac_ca_mfs_h
+/* Cesar project {{{
+ *
+ * Copyright (C) 2007 Spidcom
+ *
+ * <<<Licence>>>
+ *
+ * }}} */
+/**
+ * \file mac/ca/mfs.h
+ * \brief Channel Access related definitions for MFS TX.
+ * \ingroup mac_ca
+ */
+
+/** MFS state according to Channel Access. */
+enum ca_mfs_state_t
+{
+ CA_MFS_STATE_UNKNOWN, /*< MFS unknown to CA, also if it contains no
+ PB. */
+ CA_MFS_STATE_PRIO_QUEUED, /*< MFS queued to CSMA CA MFS heap. */
+ CA_MFS_STATE_CFP_QUEUED, /*< MFS available for TDMA. */
+};
+typedef enum ca_mfs_state_t ca_mfs_state_t;
+
+#endif /* mac_ca_mfs_h */
diff --git a/mac/ca/src/access.c b/mac/ca/src/access.c
new file mode 100644
index 0000000000..1cd69508dc
--- /dev/null
+++ b/mac/ca/src/access.c
@@ -0,0 +1,218 @@
+/* Cesar project {{{
+ *
+ * Copyright (C) 2007 Spidcom
+ *
+ * <<<Licence>>>
+ *
+ * }}} */
+/**
+ * \file mac/ca/src/access.c
+ * \brief ACCESS event and VCS related functions.
+ * \ingroup mac_ca
+ */
+#include "common/std.h"
+
+#include "mac/common/timings.h"
+#include "mac/ca/ca.h"
+
+#include "hal/phy/phy.h"
+
+#include "mac/ca/inc/context.h"
+#include "mac/ca/inc/alloc.h"
+
+/**
+ * Choose a MFS TX for the given GLID.
+ * \param ctx ca context
+ * \param glid global link identifier
+ * \return MFS or NULL if none match
+ */
+static mfs_tx_t *
+ca_access_choose_mfs_tx (ca_t *ctx, uint glid);
+
+void
+ca_access_vcs_restart (ca_t *ctx, u32 start_date, uint length_tck,
+ uint anticipation_tck, bool eifs)
+{
+ uint bp_i, bp_end_i, alloc_i;
+ const ca_beacon_period_t *bp;
+ const ca_schedule_t *sched;
+ u32 vcs_end_date;
+ uint glid;
+ bool idle, cfp, hybrid;
+ uint minimum_length;
+ bool new_backoff_drawn;
+ mfs_tx_t *mfs;
+ dbg_assert (ctx);
+ dbg_assert (length_tck > 0);
+ /* Find the beacon period of the start date, will search for TX
+ * opportunities in two beacon periods. */
+ vcs_end_date = start_date + length_tck;
+ bp_i = ca_alloc_find_beacon_period (ctx, start_date);
+ if (bp_i != ctx->beacon_periods_tail)
+ {
+ /* Beacon period found. */
+ bp = &ctx->beacon_periods[bp_i];
+ sched = &ctx->schedules[bp->schedule_index];
+ /* Find the allocation of the start date. */
+ alloc_i = ca_alloc_find (sched, start_date - bp->start_date);
+ idle = eifs;
+ }
+ else
+ {
+ /* Beacon period not found, use first one. */
+ bp_i = ctx->beacon_periods_head;
+ dbg_assert (bp_i != ctx->beacon_periods_tail);
+ bp = &ctx->beacon_periods[bp_i];
+ sched = &ctx->schedules[bp->schedule_index];
+ alloc_i = 0;
+ vcs_end_date = bp->start_date;
+ idle = false;
+ }
+ /* Find a suitable allocation in this beacon period or the next one. */
+ bp_end_i = CA_ALLOC_NEXT_BEACON_PERIOD (bp_i);
+ if (bp_end_i != ctx->beacon_periods_tail)
+ bp_end_i = CA_ALLOC_NEXT_BEACON_PERIOD (bp_i);
+ new_backoff_drawn = false;
+ do
+ {
+ /* Test if this allocation can be used. */
+ if (alloc_i < sched->allocations_nb
+ && sched->allocations[alloc_i].glid != MAC_LID_SPC_HOLE
+ && less_mod2p32 (vcs_end_date, bp->start_date
+ + sched->allocations[alloc_i].end_offset_tck))
+ {
+ glid = sched->allocations[alloc_i].glid;
+ mfs = ca_access_choose_mfs_tx (ctx, glid);
+ if (mfs)
+ {
+ /* TODO: test if it have pb to send. */
+ cfp = !CA_ALLOC_IS_CSMA (glid);
+ hybrid = CA_ALLOC_IS_HYBRID (ctx->config->coexistence_mode,
+ glid);
+ /* TODO: with ACK, depends of the RIFS. */
+ /* TODO: need special handling for beacons. */
+ minimum_length = MAC_PREAMBLE_TCK
+ + (hybrid ? MAC_FC_10_TCK : 0)
+ + MAC_FC_AV_TCK * ctx->config->fc_symbols_nb
+ + MAC_DX567_TCK + MAC_AIFS_TCK;
+ if (!(cfp || idle))
+ {
+ /* The backoff should be drawn now. */
+ if (new_backoff_drawn)
+ ca_backoff_cancel (ctx);
+ ca_backoff_new (ctx, mfs->cap);
+ new_backoff_drawn = true;
+ minimum_length += (2 + ctx->backoff.bc) * MAC_SLOT_TCK;
+ }
+ if (less_mod2p32 (vcs_end_date + minimum_length,
+ bp->start_date +
+ sched->allocations[alloc_i].end_offset_tck))
+ {
+ /* Fit. */
+ break;
+ }
+ }
+ }
+ /* Advance to the next allocation. */
+ if (alloc_i == sched->allocations_nb)
+ {
+ /* Next beacon period. */
+ bp_i = CA_ALLOC_NEXT_BEACON_PERIOD (bp_i);
+ if (bp_i == bp_end_i)
+ {
+ /* Give up. */
+ break;
+ }
+ bp = &ctx->beacon_periods[bp_i];
+ sched = &ctx->schedules[bp->schedule_index];
+ alloc_i = 0;
+ vcs_end_date = bp->start_date;
+ }
+ else
+ {
+ /* Next allocation. */
+ vcs_end_date = bp->start_date
+ + sched->allocations[alloc_i].end_offset_tck;
+ alloc_i++;
+ }
+ /* IDLE for EIFS only works for the first allocation. If we land in
+ * another allocation, the synchronisation is done. */
+ idle = false;
+ } while (1);
+ /* TODO: combine with an MME. */
+ /* Was a allocation found? */
+ if (bp_i != bp_end_i)
+ {
+ /* Setup ACCESS for this allocation. */
+ if (!(cfp || idle))
+ {
+ phy_access_backoff_start (ctx->phy, vcs_end_date, mfs->cap);
+ phy_access_timer_program (ctx->phy, vcs_end_date
+ + (ctx->backoff.bc + 2) * MAC_SLOT_TCK
+ - anticipation_tck);
+ }
+ else
+ {
+ phy_access_timer_program (ctx->phy, vcs_end_date
+ - anticipation_tck);
+ }
+ /* Record parameters if VCS need to be reprogrammed. */
+ ctx->vcs_start_date = start_date;
+ ctx->vcs_length_tck = length_tck;
+ ctx->vcs_eifs = eifs;
+ ctx->anticipation_tck = anticipation_tck;
+ }
+ else
+ {
+ ctx->vcs_length_tck = 0;
+ }
+}
+
+void
+ca_access_program (ca_t *ctx, u32 date, uint anticipation_tck)
+{
+ dbg_assert (ctx);
+ phy_access_timer_program (ctx->phy, date - anticipation_tck);
+}
+
+void
+ca_access_grant (ca_t *ctx, mfs_tx_t *mfs, uint duration_tck)
+{
+ dbg_assert (ctx);
+ if (!mfs)
+ {
+ /* Choose an MFS. */
+ ctx->access_param.mfs =
+ PARENT_OF (mfs_tx_t, link, heap_get_root (&ctx->mfs_heap));
+ }
+ else
+ {
+ /* Use the given one. */
+ ctx->access_param.mfs = mfs;
+ }
+ ctx->access_param.duration_tck = duration_tck;
+ ctx->access_param.content = false;
+}
+
+const ca_access_param_t *
+ca_access_get_param (ca_t *ctx)
+{
+ dbg_assert (ctx);
+ return &ctx->access_param;
+}
+
+static mfs_tx_t *
+ca_access_choose_mfs_tx (ca_t *ctx, uint glid)
+{
+ dbg_assert (ctx);
+ dbg_assert (glid >= MAC_GLID_MIN);
+ /* If GLID, this is a CFP allocation, else choose the MFS with the greater
+ * priority. */
+ if (glid <= MAC_GLID_MAX)
+ return mac_store_mfs_get_tx (ctx->store, false, false, glid, 0);
+ else if (CA_ALLOC_IS_CSMA (glid))
+ return PARENT_OF (mfs_tx_t, link, heap_get_root (&ctx->mfs_heap));
+ else /* \todo support beacon TX. */
+ return NULL;
+}
+
diff --git a/mac/ca/src/alloc.c b/mac/ca/src/alloc.c
new file mode 100644
index 0000000000..4d0926ccaa
--- /dev/null
+++ b/mac/ca/src/alloc.c
@@ -0,0 +1,123 @@
+/* Cesar project {{{
+ *
+ * Copyright (C) 2007 Spidcom
+ *
+ * <<<Licence>>>
+ *
+ * }}} */
+/**
+ * \file mac/ca/src/alloc.c
+ * \brief Beacon period and schedule related functions.
+ * \ingroup mac_ca
+ */
+#include "common/std.h"
+
+#include "mac/ca/inc/context.h"
+#include "mac/ca/inc/alloc.h"
+#include "hal/phy/phy.h"
+
+uint
+ca_alloc_find_beacon_period (const ca_t *ctx, u32 date)
+{
+ uint pi, i;
+ dbg_assert (ctx);
+ pi = ctx->beacon_periods_tail;
+ for (i = ctx->beacon_periods_head;
+ i != ctx->beacon_periods_tail
+ && lesseq_mod2p32 (ctx->beacon_periods[i].start_date, date);
+ pi = i, i = CA_ALLOC_NEXT_BEACON_PERIOD (i))
+ ;
+ return pi;
+}
+
+uint
+ca_alloc_find (const ca_schedule_t *sched, uint offset_tck)
+{
+ uint a, b, m;
+ /* Dichotomy search. */
+ a = 0;
+ b = sched->allocations_nb;
+ while (a != b)
+ {
+ m = (a + b) / 2;
+ if (less_mod2p32 (offset_tck, sched->allocations[m].end_offset_tck))
+ b = m;
+ else
+ a = m + 1;
+ }
+ return a;
+}
+
+ca_schedule_t *
+ca_alloc_get_schedule (ca_t *ctx, uint index)
+{
+ uint i;
+ dbg_assert (ctx);
+ /* Check this schedule is not used. */
+ for (i = ctx->beacon_periods_head;
+ i != ctx->beacon_periods_tail;
+ i = CA_ALLOC_NEXT_BEACON_PERIOD (i))
+ dbg_assert (ctx->beacon_periods[i].schedule_index != index);
+ return &ctx->schedules[index];
+}
+
+void
+ca_alloc_update_beacon_periods (ca_t *ctx,
+ ca_beacon_period_t *beacon_periods,
+ uint beacon_periods_nb)
+{
+ u32 now;
+ uint i, j;
+ bool non_smooth = false;
+ dbg_assert (ctx);
+ dbg_assert (beacon_periods);
+ dbg_assert (beacon_periods_nb > 0
+ && beacon_periods_nb < CA_BEACON_PERIOD_NB - 1);
+ /* Eliminate expired beacon period from context. */
+ for (i = ctx->beacon_periods_head;
+ i != ctx->beacon_periods_tail
+ && less_mod2p32 (ctx->beacon_periods[i].start_date,
+ beacon_periods[0].start_date);
+ i = CA_ALLOC_NEXT_BEACON_PERIOD (i))
+ ;
+ ctx->beacon_periods_head = i;
+ /* First beacon period provided should be the current one (actually, it
+ * might be the second one...). */
+ now = phy_date (ctx->phy);
+ dbg_assert (lesseq_mod2p32 (beacon_periods[0].start_date, now)
+ && (beacon_periods_nb < 2
+ || less_mod2p32 (now, beacon_periods[1].start_date)));
+ /* Update the first and second period.
+ * This step aims at checking whether the current scheduled access should
+ * be updated. TODO It should be reworked. For example, a better
+ * approach could process as a regular update to work out if the same
+ * results are obtained. I suspect the current approach to give both
+ * false positives and negatives, to not work anymore as soon as NTB plays
+ * against us, or actually, to not work at all... */
+ for (j = 0, i = ctx->beacon_periods_head;
+ j < 2 && j < beacon_periods_nb && i != ctx->beacon_periods_tail;
+ j++, i = CA_ALLOC_NEXT_BEACON_PERIOD (i))
+ {
+ if (ctx->beacon_periods[i].start_date != beacon_periods[j].start_date
+ || (ctx->beacon_periods[i].schedule_index
+ != beacon_periods[j].schedule_index))
+ {
+ /* Non-smooth update. */
+ non_smooth = true;
+ break;
+ }
+ }
+ /* Update other periods. */
+ for (; j < beacon_periods_nb; j++, i = CA_ALLOC_NEXT_BEACON_PERIOD (i))
+ {
+ ctx->beacon_periods[i].start_date = beacon_periods[j].start_date;
+ ctx->beacon_periods[i].schedule_index =
+ beacon_periods[j].schedule_index;
+ }
+ ctx->beacon_periods_tail = i;
+ dbg_assert ((ctx->beacon_periods_tail - ctx->beacon_periods_head +
+ CA_BEACON_PERIOD_NB) % CA_BEACON_PERIOD_NB ==
+ beacon_periods_nb);
+ /* TODO Handle non-smooth updates. */
+}
+
diff --git a/mac/ca/src/backoff.c b/mac/ca/src/backoff.c
index 182dda4f4b..e6acd5b34a 100644
--- a/mac/ca/src/backoff.c
+++ b/mac/ca/src/backoff.c
@@ -51,6 +51,7 @@ ca_backoff_new (ca_t *ctx, uint cap)
uint cw = cw_by_capmsb_by_pbc[cap >> 1][bpcm];
if (cw != ctx->backoff.cw)
{
+ /* Handle CAP change. */
ctx->backoff.cw = cw;
ctx->backoff.bc = lib_rnd32 (&ctx->backoff.rnd_context)
& ctx->backoff.cw;
@@ -78,3 +79,11 @@ ca_backoff_success (ca_t *ctx)
ctx->backoff.bpc = 0;
}
+void
+ca_backoff_cancel (ca_t *ctx)
+{
+ dbg_assert (ctx);
+ ctx->backoff.bc++;
+ ctx->backoff.dc++;
+}
+
diff --git a/mac/ca/src/ca.c b/mac/ca/src/ca.c
new file mode 100644
index 0000000000..a5785ff882
--- /dev/null
+++ b/mac/ca/src/ca.c
@@ -0,0 +1,97 @@
+/* Cesar project {{{
+ *
+ * Copyright (C) 2007 Spidcom
+ *
+ * <<<Licence>>>
+ *
+ * }}} */
+/**
+ * \file mac/ca/src/ca.c
+ * \brief Channel Access main implementation file.
+ * \ingroup mac_ca
+ */
+#include "common/std.h"
+
+#include "mac/ca/inc/context.h"
+#include "mac/common/timings.h"
+
+ca_t ca_global;
+
+/**
+ * MFS priority comparaison function.
+ * \param left left hand MFS
+ * \param right right hand MFS
+ * \return true iff left has a greater priority than right
+ */
+static bool
+ca_mfs_less (heap_node_t *left, heap_node_t *right);
+
+ca_t *
+ca_init (phy_t *phy, mac_config_t *config, mac_store_t *store)
+{
+ dbg_assert (phy);
+ dbg_assert (config);
+ dbg_assert (store);
+ ca_t *ctx = &ca_global;
+ ctx->phy = phy;
+ ctx->config = config;
+ ctx->store = store;
+ ctx->access_param.mfs = NULL;
+ ctx->access_param.access_date = 0;
+ ctx->access_param.duration_tck = 0;
+ ctx->access_param.cfp = false;
+ ctx->access_param.content = false;
+ ctx->vcs_start_date = 0;
+ ctx->vcs_length_tck = 0;
+ ctx->vcs_eifs = false;
+ ctx->anticipation_tck = 0;
+ ca_backoff_init (ctx);
+ ctx->beacon_periods_head = ctx->beacon_periods_tail = 0;
+ heap_init (&ctx->mfs_heap, ca_mfs_less);
+ return ctx;
+}
+
+void
+ca_uninit (ca_t *ctx)
+{
+ dbg_assert (ctx);
+}
+
+void
+ca_mfs_init (ca_t *ctx, mfs_tx_t *mfs)
+{
+ dbg_assert (ctx);
+ dbg_assert (mfs);
+ heap_node_init (&mfs->link);
+ mfs->ca_state = CA_MFS_STATE_UNKNOWN;
+}
+
+void
+ca_mfs_uninit (ca_t *ctx, mfs_tx_t *mfs)
+{
+ dbg_assert (ctx);
+ dbg_assert (mfs);
+ if (mfs->ca_state == CA_MFS_STATE_PRIO_QUEUED)
+ {
+ heap_remove (&ctx->mfs_heap, &mfs->link);
+ }
+ mfs->ca_state = CA_MFS_STATE_UNKNOWN;
+}
+
+void
+ca_mfs_update (ca_t *ctx, mfs_tx_t *mfs)
+{
+ dbg_assert (ctx);
+ dbg_assert (mfs);
+ //heap_adjust (&ctx->mfs_heap, &mfs->link);
+}
+
+static bool
+ca_mfs_less (heap_node_t *left, heap_node_t *right)
+{
+ mfs_tx_t *lmfs = PARENT_OF (mfs_tx_t, link, left);
+ mfs_tx_t *rmfs = PARENT_OF (mfs_tx_t, link, right);
+ /* TODO: write a real comparison function. */
+ return lmfs->cap < rmfs->cap;
+}
+
diff --git a/mac/ca/test/backoff/Makefile b/mac/ca/test/backoff/Makefile
deleted file mode 100644
index 85dd429477..0000000000
--- a/mac/ca/test/backoff/Makefile
+++ /dev/null
@@ -1,7 +0,0 @@
-BASE = ../../../..
-
-HOST_PROGRAMS = test_backoff
-test_backoff_SOURCES = test_backoff.c
-test_backoff_MODULES = lib mac/ca
-
-include $(BASE)/common/make/top.mk
diff --git a/mac/ca/test/ca/Makefile b/mac/ca/test/ca/Makefile
new file mode 100644
index 0000000000..ed0f14b6b7
--- /dev/null
+++ b/mac/ca/test/ca/Makefile
@@ -0,0 +1,7 @@
+BASE = ../../../..
+
+HOST_PROGRAMS = test_ca
+test_ca_SOURCES = test_ca.c test_backoff.c test_alloc.c phy_stub.c
+test_ca_MODULES = lib mac/ca mac/common
+
+include $(BASE)/common/make/top.mk
diff --git a/mac/ca/test/ca/inc/phy_stub.h b/mac/ca/test/ca/inc/phy_stub.h
new file mode 100644
index 0000000000..b1a4746d35
--- /dev/null
+++ b/mac/ca/test/ca/inc/phy_stub.h
@@ -0,0 +1,23 @@
+#ifndef inc_phy_stub_h
+#define inc_phy_stub_h
+/* Cesar project {{{
+ *
+ * Copyright (C) 2007 Spidcom
+ *
+ * <<<Licence>>>
+ *
+ * }}} */
+/**
+ * \file inc/phy_stub.h
+ * \brief HAL Phy stub.
+ * \ingroup test
+ */
+
+/** Stub phy structure. */
+struct phy_t
+{
+ u32 date;
+};
+/* Forward declaration in hal/phy/forward.h. */
+
+#endif /* inc_phy_stub_h */
diff --git a/mac/ca/test/ca/src/phy_stub.c b/mac/ca/test/ca/src/phy_stub.c
new file mode 100644
index 0000000000..8ca4ccef22
--- /dev/null
+++ b/mac/ca/test/ca/src/phy_stub.c
@@ -0,0 +1,55 @@
+/* Cesar project {{{
+ *
+ * Copyright (C) 2007 Spidcom
+ *
+ * <<<Licence>>>
+ *
+ * }}} */
+/**
+ * \file src/phy_stub.c
+ * \brief HAL Phy stub.
+ * \ingroup test
+ */
+#include "common/std.h"
+
+#include "hal/phy/phy.h"
+
+#include "inc/phy_stub.h"
+
+phy_t global_phy;
+
+phy_t *
+phy_init (void *user_data, phy_rx_fc_cb_t rx_fc_cb, phy_access_cb_t access_cb,
+ phy_access_conf_cb_t access_conf_cb, phy_pbdma_cb_t pbdma_cb,
+ phy_deferred_cb_t deferred_cb)
+{
+ phy_t *ctx = &global_phy;
+ ctx->date = 0;
+ return ctx;
+}
+
+void
+phy_uninit (phy_t *ctx)
+{
+ dbg_assert (ctx);
+}
+
+void
+phy_access_backoff_start (phy_t *ctx, u32 date, uint cap)
+{
+ dbg_assert (ctx);
+}
+
+void
+phy_access_timer_program (phy_t *ctx, u32 date)
+{
+ dbg_assert (ctx);
+}
+
+u32
+phy_date (phy_t *ctx)
+{
+ dbg_assert (ctx);
+ return ctx->date;
+}
+
diff --git a/mac/ca/test/ca/src/test_alloc.c b/mac/ca/test/ca/src/test_alloc.c
new file mode 100644
index 0000000000..809f9ecd6e
--- /dev/null
+++ b/mac/ca/test/ca/src/test_alloc.c
@@ -0,0 +1,186 @@
+/* Cesar project {{{
+ *
+ * Copyright (C) 2007 Spidcom
+ *
+ * <<<Licence>>>
+ *
+ * }}} */
+/**
+ * \file src/test_alloc.c
+ * \brief Test allocations code.
+ * \ingroup test
+ */
+#include "common/std.h"
+
+#include "mac/ca/inc/context.h"
+#include "mac/ca/inc/alloc.h"
+#include "mac/common/timings.h"
+
+#include "hal/phy/phy.h"
+#include "inc/phy_stub.h"
+
+#include "lib/test.h"
+
+#define NB_ITER 100000
+
+void
+alloc_basic_test_case (test_t t)
+{
+ uint i, j, k;
+ lib_rnd_t rnd[1];
+ phy_t *phy;
+ mac_config_t config;
+ mac_store_t *store;
+ ca_t *ca;
+ test_case_begin (t, "basic");
+ /* Initialise. */
+ phy = phy_init (NULL, NULL, NULL, NULL, NULL, NULL);
+ config.tei = 1;
+ config.coexistence_mode = MAC_COEXISTENCE_SHARED_CSMA_HYBRID_MODE;
+ config.fc_symbols_nb = 1;
+ store = mac_store_init ();
+ ca = ca_init (phy, &config, store);
+ lib_rnd_init (rnd, 1234);
+ test_begin (t, "is hybrid")
+ {
+ struct
+ {
+ u8 lid;
+ mac_coexistence_mode_t coex;
+ bool expect;
+ } is_hybrid_tab[] = {
+ { 0x80, MAC_COEXISTENCE_AV_ONLY_MODE, false },
+ { 0x8a, MAC_COEXISTENCE_SHARED_CSMA_HYBRID_MODE, false },
+ { 0xa2, MAC_COEXISTENCE_FULL_HYBRID_MODE, true },
+ { 0xcd, MAC_COEXISTENCE_HYBRID_DELIMITERS_MODE, true },
+ { MAC_LID_DISCOVER, MAC_COEXISTENCE_AV_ONLY_MODE, true },
+ { MAC_LID_DISCOVER, MAC_COEXISTENCE_SHARED_CSMA_HYBRID_MODE, true },
+ { MAC_LID_DISCOVER, MAC_COEXISTENCE_FULL_HYBRID_MODE, true },
+ { MAC_LID_DISCOVER, MAC_COEXISTENCE_HYBRID_DELIMITERS_MODE, true },
+ { MAC_LID_SHARED_CSMA, MAC_COEXISTENCE_AV_ONLY_MODE, false },
+ { MAC_LID_SHARED_CSMA, MAC_COEXISTENCE_SHARED_CSMA_HYBRID_MODE, true },
+ { MAC_LID_SHARED_CSMA, MAC_COEXISTENCE_FULL_HYBRID_MODE, true },
+ { MAC_LID_SHARED_CSMA, MAC_COEXISTENCE_HYBRID_DELIMITERS_MODE, true },
+ { MAC_LID_LOCAL_CSMA, MAC_COEXISTENCE_AV_ONLY_MODE, false },
+ { MAC_LID_LOCAL_CSMA, MAC_COEXISTENCE_SHARED_CSMA_HYBRID_MODE, false },
+ { MAC_LID_LOCAL_CSMA, MAC_COEXISTENCE_FULL_HYBRID_MODE, true },
+ { MAC_LID_LOCAL_CSMA, MAC_COEXISTENCE_HYBRID_DELIMITERS_MODE, true },
+ // { MAC_LID_CFPI, ? },
+ };
+ for (i = 0; i < COUNT (is_hybrid_tab); i++)
+ {
+ test_fail_unless (
+ CA_ALLOC_IS_HYBRID (is_hybrid_tab[i].coex,
+ is_hybrid_tab[i].lid) ==
+ is_hybrid_tab[i].expect, "is hybrid mismatch i=%d", i);
+ }
+ } test_end;
+ test_begin (t, "beacon periods")
+ {
+ const int beacon_period_length = MAC_MS_TO_TCK (1000 / 50);
+ ca_beacon_period_t periods[CA_BEACON_PERIOD_NB];
+ uint periods_nb = 0;
+ uint periods_nb_new;
+ uint used;
+ for (i = 0; i < NB_ITER; i++)
+ {
+ phy->date = i * beacon_period_length + beacon_period_length / 3;
+ periods_nb_new =
+ lib_rnd_uniform (rnd, CA_BEACON_PERIOD_NB - 2) + 1;
+ for (j = 0; j < periods_nb_new; j++)
+ {
+ /* Change older periods, set new periods. */
+ if (j + 1 >= periods_nb
+ || lib_rnd_flip_coin (rnd, LIB_RND_RATIO (0.3)))
+ {
+ periods[j].start_date = (i + j) * beacon_period_length
+ + lib_rnd_uniform (rnd, beacon_period_length / 100)
+ - beacon_period_length / 200;
+ periods[j].schedule_index =
+ lib_rnd_uniform (rnd, CA_SCHEDULE_NB);
+ }
+ else
+ {
+ periods[j] = periods[j + 1];
+ }
+ }
+ periods_nb = periods_nb_new;
+ /* Update CA periods. */
+ ca_alloc_update_beacon_periods (ca, periods, periods_nb);
+ /* Check the update. */
+ for (j = 0, k = ca->beacon_periods_head; j < periods_nb;
+ j++, k = CA_ALLOC_NEXT_BEACON_PERIOD (k))
+ {
+ test_fail_unless (k != ca->beacon_periods_tail);
+ test_fail_unless ((ca->beacon_periods[k].start_date
+ == periods[j].start_date)
+ && (ca->beacon_periods[k].schedule_index
+ == periods[j].schedule_index));
+ }
+ test_fail_unless (k == ca->beacon_periods_tail);
+ /* Test get_schedule. */
+ used = 0;
+ for (j = 0; j < periods_nb; j++)
+ {
+ dbg_assert (periods[j].schedule_index < CA_SCHEDULE_NB);
+ used |= 1 << periods[j].schedule_index;
+ }
+ for (j = 0; used; j++, used >>= 1)
+ {
+ if (!(used & 1))
+ ca_alloc_get_schedule (ca, j);
+ }
+ /* Test find_beacon_period. */
+ for (j = 0, k = ca->beacon_periods_head; j < periods_nb;
+ j++, k = CA_ALLOC_NEXT_BEACON_PERIOD (k))
+ {
+ test_fail_unless (ca_alloc_find_beacon_period (
+ ca, periods[j].start_date) == k);
+ test_fail_unless (ca_alloc_find_beacon_period (
+ ca, periods[j].start_date
+ + beacon_period_length / 3) == k);
+ }
+ }
+ } test_end;
+ test_begin (t, "alloc find")
+ {
+ ca_schedule_t schedule;
+ uint end;
+ for (i = 0; i < NB_ITER / CA_SCHEDULE_SIZE; i++)
+ {
+ schedule.allocations_nb = lib_rnd_uniform (rnd, CA_SCHEDULE_SIZE);
+ end = 0;
+ for (j = 0; j < schedule.allocations_nb; j++)
+ {
+ end = end + 2 + lib_rnd_uniform (
+ rnd, (1 << 24)
+ - (schedule.allocations_nb - j) * 2
+ - end - 2);
+ schedule.allocations[j].end_offset_tck = end;
+ schedule.allocations[j].glid = 0;
+ }
+ end = 0;
+ for (j = 0; j < schedule.allocations_nb; j++)
+ {
+ test_fail_unless (ca_alloc_find (&schedule, end) == j);
+ test_fail_unless (ca_alloc_find (&schedule, end + 1) == j);
+ end = schedule.allocations[j].end_offset_tck;
+ test_fail_unless (ca_alloc_find (&schedule, end) == j + 1);
+ test_fail_unless (ca_alloc_find (&schedule, end + 1)
+ == j + 1);
+ }
+ }
+ } test_end;
+ /* Uninitialise. */
+ ca_uninit (ca);
+ phy_uninit (phy);
+ mac_store_uninit (store);
+}
+
+void
+alloc_test_suite (test_t t)
+{
+ test_suite_begin (t, "alloc");
+ alloc_basic_test_case (t);
+}
+
diff --git a/mac/ca/test/backoff/src/test_backoff.c b/mac/ca/test/ca/src/test_backoff.c
index cd524f2c7f..82b14248e0 100644
--- a/mac/ca/test/backoff/src/test_backoff.c
+++ b/mac/ca/test/ca/src/test_backoff.c
@@ -18,10 +18,10 @@
#define NB_ITER 1000000
-void
+static void
backoff_basic_test_case (test_t t)
{
- uint i;
+ uint i, j;
uint cap = 0, slot_count = 0, bpcm;
lib_rnd_t rnd;
ca_t ca;
@@ -50,17 +50,23 @@ backoff_basic_test_case (test_t t)
for (i = 0; i < NB_ITER; i++)
{
/* New frame. */
- if (lib_rnd32 (&rnd) >= same_cap_ratio)
- {
+ if (!lib_rnd_flip_coin (&rnd, same_cap_ratio))
cap = lib_rnd32 (&rnd) % 4;
- }
ca_backoff_new (&ca, cap);
+ /* Test cancelation. */
+ for (j = lib_rnd_uniform (&rnd, 3); j; j--)
+ {
+ ca_backoff_cancel (&ca);
+ if (!lib_rnd_flip_coin (&rnd, same_cap_ratio))
+ cap = lib_rnd32 (&rnd) % 4;
+ ca_backoff_new (&ca, cap);
+ }
/* Check backoff. Throw some general rules... */
test_verbose_print ("cap = %d, bpc = %d, cw = %2d, bc = %2d, "
"dc = %2d ", cap, ca.backoff.bpc,
ca.backoff.cw, ca.backoff.bc, ca.backoff.dc);
test_verbose_print ("last_success = %d, last_bpc = %d, "
- "last_bc = %2d, slot_count = %2d\n",
+ "last_bc = %2d, slot_count = %2d",
last_success, last_bpc, last_bc, slot_count);
bpcm = MIN (3u, ca.backoff.bpc - 1);
test_fail_unless (ca.backoff.cw == cw_table[cap][bpcm]);
@@ -87,7 +93,7 @@ backoff_basic_test_case (test_t t)
/* Defer or success? */
slot_count = lib_rnd_uniform (&rnd, ca.backoff.bc + 1);
ca_backoff_deferred (&ca, slot_count);
- last_success = lib_rnd32 (&rnd) < success_ratio;
+ last_success = lib_rnd_flip_coin (&rnd, success_ratio);
if (last_success)
{
ca_backoff_success (&ca);
@@ -103,12 +109,3 @@ backoff_test_suite (test_t t)
backoff_basic_test_case (t);
}
-int
-main (int argc, char **argv)
-{
- test_t t;
- test_init (t, argc, argv);
- backoff_test_suite (t);
- test_result (t);
- return test_nb_failed (t) == 0 ? 0 : 1;
-}
diff --git a/mac/ca/test/ca/src/test_ca.c b/mac/ca/test/ca/src/test_ca.c
new file mode 100644
index 0000000000..cecc17bcd5
--- /dev/null
+++ b/mac/ca/test/ca/src/test_ca.c
@@ -0,0 +1,32 @@
+/* Cesar project {{{
+ *
+ * Copyright (C) 2007 Spidcom
+ *
+ * <<<Licence>>>
+ *
+ * }}} */
+/**
+ * \file src/test_ca.c
+ * \brief Test Channel Access.
+ * \ingroup test
+ */
+#include "common/std.h"
+
+#include "lib/test.h"
+
+void
+backoff_test_suite (test_t t);
+
+void
+alloc_test_suite (test_t t);
+
+int
+main (int argc, char **argv)
+{
+ test_t t;
+ test_init (t, argc, argv);
+ backoff_test_suite (t);
+ alloc_test_suite (t);
+ test_result (t);
+ return test_nb_failed (t) == 0 ? 0 : 1;
+}