--- /dev/null
+ /*
+ * @file sched_wrr.c
+ * @brief Weighted Round-Robin Scheduling Module for UltraMonkey-L7
+ * @auther nakai norihisa.
+ * August 2007
+ *
+ * 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/>.
+ *
+ **********************************************************************/
+
+#include <sys/types.h>
+#include <netinet/in.h>
+#include <unistd.h>
+#include <stdlib.h>
+#include <stdio.h>
+#include <glib.h>
+#include <string.h>
+#include "l7vs.h"
+#include "l7vs_conn.h"
+#include "l7vs_service.h"
+#include "l7vs_sched.h"
+#include "l7vs_dest.h"
+
+#define IS_SCHEDWRR_DEBUG if( LOG_LV_DEBUG == IS_DEBUG<struct l7vs_scheduler>( sched_wrr_scheduler, LOG_CAT_L7VSD_SCHEDULE ))
+#define SCHED_DEBUG(X,Y...) PUT_LOG_DEBUG( sched_wrr_scheduler, LOG_CAT_L7VSD_SCHEDULE, X, ##Y )
+#define SCHED_INFO(X,Y...) PUT_LOG_INFO( sched_wrr_scheduler, LOG_CAT_L7VSD_SCHEDULE, X, ##Y )
+#define SCHED_WARN(X,Y...) PUT_LOG_WARN( sched_wrr_scheduler, LOG_CAT_L7VSD_SCHEDULE, X, ##Y )
+#define SCHED_ERROR(X,Y...) PUT_LOG_ERROR( sched_wrr_scheduler, LOG_CAT_L7VSD_SCHEDULE, X, ##Y )
+#define SCHED_FATAL(X,Y...) PUT_LOG_FATAL( sched_wrr_scheduler, LOG_CAT_L7VSD_SCHEDULE, X, ##Y )
+
+#define MAX_VS 128
+#define VS_INITIALIZED 1
+#define VS_NOTINUSE 0
+
+struct wrr_weights {
+ int currentWeight; /*! Current Weight */
+ int maxWeight; /*! Max of Weight */
+ int gcd; /*! GCD of dest_list */
+};
+
+struct servicedest_contenor{
+ handle_t handle;
+ struct in_addr addr;
+ u_short port;
+};
+
+GList* servicedest_list;
+
+static int vs_initialized_flags[MAX_VS];
+static struct wrr_weights *vs_weights[MAX_VS];
+
+static void fini(void);
+struct l7vs_dest* l7vs_sched_wrr_schedule(struct l7vs_service*, struct l7vs_conn*);
+static int l7vs_sched_wrr_service_init(struct l7vs_service*);
+static int l7vs_sched_wrr_recalc(struct l7vs_service*);
+static int l7vs_sched_wrr_getMaxWeight(struct l7vs_service*);
+static int l7vs_sched_wrr_gcd(int, int);
+static int l7vs_sched_wrr_getGCD(struct l7vs_service*);
+static GList* l7vs_sched_wrr_search_suitableRS(GList*, int);
+
+
+static struct l7vs_scheduler sched_wrr_scheduler = {
+ NULL,
+ "wrr",
+ 0,
+ l7vs_sched_wrr_schedule,
+ NULL,
+ NULL,
+ fini,
+ NULL, /*! loglevel get function */
+ NULL, /*! debug log put function */
+ NULL, /*! info log put function */
+ NULL, /*! warn log put function */
+ NULL, /*! error log put function */
+ NULL /*! fatal log put function */
+};
+
+extern "C" struct l7vs_scheduler* init(void *handle){
+ IS_SCHEDWRR_DEBUG{
+ SCHED_DEBUG(39, "in_function extern \"C\" struct l7vs_scheduler* init( void* handle ) : handle = %p" , handle );
+ }
+ servicedest_list = NULL;
+ memset(vs_initialized_flags, VS_NOTINUSE, sizeof (vs_initialized_flags));
+ memset(vs_weights, 0, sizeof (vs_weights));
+ sched_wrr_scheduler.handle = handle;
+ IS_SCHEDWRR_DEBUG{
+ SCHED_DEBUG(40, "out_function extern \"C\" struct l7vs_scheduler* init( void* handle ) : return = %p" , &sched_wrr_scheduler );
+ }
+ return &sched_wrr_scheduler;
+}
+
+void fini(void){
+ IS_SCHEDWRR_DEBUG{
+ SCHED_DEBUG(41, "in_function void fini(void)" );
+ }
+
+ int i;
+ GList* ptr = NULL;
+
+ for (i = 0; i < MAX_VS; ++i) {
+ if (vs_initialized_flags[i]) {
+ if(vs_weights[i] != NULL){
+ IS_SCHEDWRR_DEBUG{
+ SCHED_DEBUG(42, "virtual service[%d] weight memory free: address = %p", i , vs_weights[i] );
+ }
+ free(vs_weights[i]);
+ vs_weights[i] = NULL;
+ }
+ vs_initialized_flags[i] = VS_NOTINUSE;
+ }
+ }
+
+ for( ptr = g_list_first(servicedest_list); ptr; ptr = g_list_next(ptr) ){
+ IS_SCHEDWRR_DEBUG{
+ SCHED_DEBUG(43, "service dest list contenor data memory free: address = %p", ptr->data );
+ }
+ free( ptr->data );
+ ptr->data = NULL;
+ }
+ g_list_free( servicedest_list );
+ servicedest_list = NULL;
+}
+
+
+struct l7vs_dest* l7vs_sched_wrr_schedule(struct l7vs_service *srv, struct l7vs_conn *conn){
+ IS_SCHEDWRR_DEBUG{
+ SCHED_DEBUG(44, "in_function stuct l7vs_dest* l7vs_sched_wrr_schedule( struct l7vs_service* srv, struct l7vs_conn* conn ) srv = %p, conn = %p ", srv, conn );
+ }
+
+ struct l7vs_dest *dest;
+ GList* active_dest_list = NULL;
+ GList* ptr;
+ GList *now = NULL;
+
+ if(srv == NULL || srv->handle >= MAX_VS || srv->dest_list == NULL || srv->dest_list->data == NULL)
+ {
+ SCHED_WARN(1, " service pointer is NULL or service handle is MaxHandle over or service dest list is NULL or service dest list data pointer is NULL" );
+ dest = NULL;
+ goto OUT;
+ }
+
+ //create active dest
+ for( ptr = g_list_first( srv->dest_list ); ptr; ptr = g_list_next(ptr) ){
+ if( ((struct l7vs_dest*) ( ptr->data ))->weight > 0 ) active_dest_list = g_list_append( active_dest_list, ptr->data );
+ }
+ if( !active_dest_list ) {
+ IS_SCHEDWRR_DEBUG{
+ SCHED_DEBUG(45, " don't serch wieght > 0 dests. not scheduling." );
+ }
+ dest = NULL;
+ goto OUT;
+ }
+
+ if (vs_initialized_flags[srv->handle] == VS_NOTINUSE) {
+
+ if (l7vs_sched_wrr_service_init(srv) == -1) {
+ SCHED_WARN(2, "l7vs_sched_wrr_service_init is error don't scheduling." );
+ dest = NULL;
+ goto OUT;
+ }
+
+ vs_weights[srv->handle]->currentWeight = vs_weights[srv->handle]->maxWeight;
+ } else {
+ if (l7vs_sched_wrr_recalc(srv) != 0) {
+ SCHED_WARN(3, "l7vs_sched_wrr_recalc is error don't scheduling." );
+ dest = NULL;
+ goto OUT;
+ }
+ }
+
+ if (srv->sched_data) {
+ for( ptr = g_list_first( active_dest_list ); ptr; ptr = g_list_next(ptr) ){
+ struct l7vs_dest* tdest = (struct l7vs_dest*) ptr->data;
+ struct servicedest_contenor* contenor = (struct servicedest_contenor*) srv->sched_data;
+ if( !memcmp( &(tdest->addr.sin_addr), &(contenor->addr), sizeof( struct in_addr ) )
+ &&
+ tdest->addr.sin_port == contenor->port ){
+ now = (GList*) ptr;
+ break;
+ }
+ }
+ }
+ if (now == NULL || srv->sched_data == NULL) {
+ struct servicedest_contenor* contenor = (struct servicedest_contenor*) malloc( sizeof( struct servicedest_contenor ) );
+ IS_SCHEDWRR_DEBUG{
+ SCHED_DEBUG(46, "memory allocate struct service contenor. contenor address = %p" , contenor );
+ }
+ now = g_list_first( active_dest_list );
+ struct l7vs_dest* tdest = ( struct l7vs_dest* ) now->data;
+ contenor->handle = srv->handle;
+ contenor->addr = tdest->addr.sin_addr;
+ contenor->port = tdest->addr.sin_port;
+ servicedest_list = g_list_append( servicedest_list, contenor );
+ srv->sched_data = contenor;
+ }
+
+ while (1)
+ {
+ if (((struct l7vs_dest*)now->data)->weight >= vs_weights[srv->handle]->currentWeight)
+ {
+ dest = (struct l7vs_dest*)now->data;
+
+ ptr = (GList*)l7vs_sched_wrr_search_suitableRS(now, vs_weights[srv->handle]->currentWeight);
+ if (ptr == NULL)
+ {
+ ptr = g_list_first(active_dest_list);
+ vs_weights[srv->handle]->currentWeight -= vs_weights[srv->handle]->gcd;
+
+ if (vs_weights[srv->handle]->currentWeight <= 0)
+ {
+ vs_weights[srv->handle]->currentWeight = vs_weights[srv->handle]->maxWeight;
+ }
+ }
+ struct servicedest_contenor* contenor = ( struct servicedest_contenor* )srv->sched_data;
+ struct l7vs_dest* tdest = (struct l7vs_dest*) ptr->data;
+ contenor->handle = srv->handle;
+ contenor->addr = tdest->addr.sin_addr;
+ contenor->port = tdest->addr.sin_port;
+ goto OUT;
+ }
+ else
+ {
+ now = g_list_next(now);
+ if (now == NULL) {
+ now = g_list_first(srv->dest_list);
+ vs_weights[srv->handle]->currentWeight -= vs_weights[srv->handle]->gcd;
+
+ if (vs_weights[srv->handle]->currentWeight <= 0) {
+ vs_weights[srv->handle]->currentWeight = vs_weights[srv->handle]->maxWeight;
+ }
+ }
+ }
+ }
+
+OUT:
+ g_list_free( active_dest_list );
+
+ IS_SCHEDWRR_DEBUG{
+ SCHED_DEBUG(47, "out_function: truct l7vs_dest* l7vs_sched_wrr_schedule(struct l7vs_service *srv, struct l7vs_conn *conn) : return = %p" , dest );
+ }
+ return dest;
+
+}
+
+
+static int l7vs_sched_wrr_service_init(struct l7vs_service *srv){
+ IS_SCHEDWRR_DEBUG{
+ SCHED_DEBUG(48, "in function static int l7vs_sched_wrr_service_init( struct l7vs_service *srv ) srv = %p" , srv );
+ }
+
+ if(srv == NULL || srv->handle >= MAX_VS){
+ SCHED_WARN(4, "l7vs_service pointer is NULL or service handle is orver MAX_VS" );
+ IS_SCHEDWRR_DEBUG{
+ SCHED_DEBUG(49, "out_function static int l7vs_sched_wrr_service_init( struct l7vs_service* srv ) : return = -1" );
+ }
+ return -1;
+ }
+
+ vs_weights[srv->handle] = (struct wrr_weights*)malloc(sizeof(struct wrr_weights));
+ IS_SCHEDWRR_DEBUG{
+ SCHED_DEBUG(50, "allocate memory struct wrr_weights. address = %p" , vs_weights[srv->handle] );
+ }
+
+ if (vs_weights[srv->handle] == NULL) {
+ SCHED_WARN(5, "don't allocate memory. vs_weights[srv->handle] is NULL" );
+ IS_SCHEDWRR_DEBUG{
+ SCHED_DEBUG(51, "out_function: static int l7vs_sched_wrr_service_init( struct l7vs_service *srv ) : return -1" );
+ }
+ return -1;
+ }
+
+ memset(vs_weights[srv->handle], 0, sizeof(struct wrr_weights));
+ vs_weights[srv->handle]->gcd = l7vs_sched_wrr_getGCD(srv);
+ if(vs_weights[srv->handle]->gcd < 0){
+ SCHED_WARN(6, "calc gcd Negative value %d", vs_weights[srv->handle]->gcd );
+ IS_SCHEDWRR_DEBUG{
+ SCHED_DEBUG(52, "out_function: static int l7vs_sched_wrr_service_init( struct l7vs_service* srv ) : return -1" );
+ }
+ return -1;
+ }
+ vs_weights[srv->handle]->maxWeight = l7vs_sched_wrr_getMaxWeight(srv);
+ if(vs_weights[srv->handle]->maxWeight < 0){
+ SCHED_WARN(7, "maxWeight is Negative value %d", vs_weights[srv->handle]->maxWeight );
+ IS_SCHEDWRR_DEBUG{
+ SCHED_DEBUG(53, "out_function: static int l7vs_sched_wrr_service_init( struct l7vs_service* srv ) : return -1" );
+ }
+ return -1;
+ }
+ vs_initialized_flags[srv->handle] = VS_INITIALIZED;
+
+ IS_SCHEDWRR_DEBUG{
+ SCHED_DEBUG(54, "out_function: static int l7vs_sched_wrr_service_init( struct l7vs_service* srv ) : return 0" );
+ }
+ return 0;
+}
+
+static int l7vs_sched_wrr_recalc(struct l7vs_service *srv){
+ IS_SCHEDWRR_DEBUG{
+ SCHED_DEBUG(55, "in_function: static int l7vs_sched_wrr_recalc( struct l7vs_serivce* srv ) : srv = %p" , srv );
+ }
+
+ if(srv == NULL || srv->handle >= MAX_VS){
+ SCHED_WARN(8, "srevice pointer is NULL or srv->handle is orver MAX_VS" );
+ IS_SCHEDWRR_DEBUG{
+ SCHED_DEBUG(56, "out_function: static int l7vs_sched_wrr_recalc( struct l7vs_service* srv ) : return -1" );
+ }
+ return -1;
+ }
+
+ if (vs_weights[srv->handle] == NULL){
+ SCHED_WARN(9, "virtual service weight is NULL (vs_weights[srv->handle])" );
+ IS_SCHEDWRR_DEBUG{
+ SCHED_DEBUG(57, "out_function: static int l7vs_sched_wrr_recalc( struct l7vs_service* srv ) : return -1" );
+ }
+ return -1;
+ }
+
+ vs_weights[srv->handle]->gcd = l7vs_sched_wrr_getGCD(srv);
+ if(vs_weights[srv->handle]->gcd < 0 ){
+ SCHED_WARN(10, "gcd is negative value = %d", vs_weights[srv->handle]->gcd );
+ IS_SCHEDWRR_DEBUG{
+ SCHED_DEBUG(58, "out_function: static int l7vs_sched_wrr_recalc( struct l7vs_service* srv ) : return -1" );
+ }
+ return -1;
+ }
+ vs_weights[srv->handle]->maxWeight = l7vs_sched_wrr_getMaxWeight(srv);
+ if(vs_weights[srv->handle]->maxWeight < 0){
+ SCHED_WARN(11, "maxWeight is negative value = %d" , vs_weights[srv->handle]->maxWeight );
+ IS_SCHEDWRR_DEBUG{
+ SCHED_DEBUG(59, "out_function: static int l7vs_sched_wrr_recalc( struct l7vs_service* srv ) : return -1" );
+ }
+ return -1;
+ }
+ if (vs_weights[srv->handle]->currentWeight > vs_weights[srv->handle]->maxWeight){
+ vs_weights[srv->handle]->currentWeight = vs_weights[srv->handle]->maxWeight;
+ }
+
+ IS_SCHEDWRR_DEBUG{
+ SCHED_DEBUG(60, "out_function: static int l7vs_sched_wrr_recalc( struct l7vs_service* srv ) : return 0" );
+ }
+ return 0;
+
+}
+
+
+static int l7vs_sched_wrr_getMaxWeight(struct l7vs_service *srv){
+ IS_SCHEDWRR_DEBUG{
+ SCHED_DEBUG(61, "in_function: static int l7vs_sched_wrr_getMaxWeight( struct l7vs_service* srv ) : srv = %p", srv );
+ }
+ GList *l, *now;
+ struct l7vs_dest *dest;
+ int weight = 0;
+
+ if(srv == NULL || srv->dest_list == NULL){
+ SCHED_WARN(12, "service pointer is NULL or service dest list is NULL" );
+ IS_SCHEDWRR_DEBUG{
+ SCHED_DEBUG(62, "out_function: static int l7vs_sched_wrr_getMaxWeight( struct l7vs_service* srv ) : return -1" );
+ }
+ return -1;
+ }
+ l = srv->dest_list;
+
+ for (now = g_list_first(l); now != NULL; now = g_list_next(now)) {
+ dest = (struct l7vs_dest*)now->data;
+ if (dest->weight > weight) {
+ weight = dest->weight;
+ }
+ }
+
+ IS_SCHEDWRR_DEBUG{
+ SCHED_DEBUG(63, "out_function: static int l7vs_sched_wrr_getMaxWeight( struct l7vs_service* srv ) : return %d" , weight );
+ }
+ return weight;
+}
+
+
+static int l7vs_sched_wrr_gcd(int a, int b){
+
+ IS_SCHEDWRR_DEBUG{
+ SCHED_DEBUG(64, "in_function: static int l7vs_sched_wrr_gcd( int a, int b ) : a = %d, b = %d" , a, b );
+ }
+ if (a == b || b == 0) {
+ IS_SCHEDWRR_DEBUG{
+ SCHED_DEBUG(65, "out_function static int l7vs_sched_wrr_gcd( int a, int b ) : return %d" , a );
+ }
+ return a;
+ }
+ else if (a > b) {
+ IS_SCHEDWRR_DEBUG{
+ SCHED_DEBUG(66, "out_function static int l7vs_sched_wrr_gcd( int a, int b ) : return l7vs_sched_wrr_gcd( a - b, b )" );
+ }
+ return l7vs_sched_wrr_gcd (a - b, b);
+ }
+ else {
+ IS_SCHEDWRR_DEBUG{
+ SCHED_DEBUG(67, "out_function static int l7vs_sched_wrr_gcd( int a, int b ) : return l7vs_svhed_wrr_gcd( b, a )" );
+ }
+ return l7vs_sched_wrr_gcd (b, a);
+ }
+}
+
+
+static int l7vs_sched_wrr_getGCD(struct l7vs_service *srv){
+ IS_SCHEDWRR_DEBUG{
+ SCHED_DEBUG(68, "in_function static int l7vs_sched_wrr_getGCD( struct l7vs_service* srv ) : srv = %p" , srv );
+ }
+ GList *now;
+ int currentGCD = 1;
+
+ if(srv == NULL || srv->dest_list == NULL || srv->dest_list->data == NULL){
+ SCHED_WARN(13, "service pointer is NULL or srv->dest_list pointer is NULL or srv->dest_list->data pointer is NULL" );
+ IS_SCHEDWRR_DEBUG{
+ SCHED_DEBUG(69, "out_function: static int l7vs_sched_wrr_getGCD( struct l7vs_service* srv ) return -1" );
+ }
+ return -1;
+ }
+
+ now = g_list_first(srv->dest_list);
+ currentGCD = ((struct l7vs_dest*)now->data)->weight;
+ now = g_list_next(now);
+
+ while (now != NULL) {
+ currentGCD = l7vs_sched_wrr_gcd(currentGCD, ((struct l7vs_dest*)now->data)->weight);
+ now = g_list_next(now);
+ }
+
+ IS_SCHEDWRR_DEBUG{
+ SCHED_DEBUG(70, "out_function: static int l7vs_sched_wrr_getGCD( struct l7vs_service* srv ) return %d", currentGCD );
+ }
+ return currentGCD;
+}
+
+static GList* l7vs_sched_wrr_search_suitableRS(GList *list, int weight){
+ IS_SCHEDWRR_DEBUG{
+ SCHED_DEBUG(71, "in_function: static GList* l7vs_sched_wrr_serch_suitableRS( GList* list, int weight) list = %p, weight = %d", list, weight );
+ }
+ GList *now, *candidate;
+
+ now = g_list_next(list);
+ candidate = NULL;
+
+ while (now != NULL) {
+ if (((struct l7vs_dest*)now->data)->weight >= weight) {
+ candidate = now;
+ goto OUT;
+ }
+ now = g_list_next(now);
+ }
+
+ OUT:
+ IS_SCHEDWRR_DEBUG{
+ SCHED_DEBUG(72, "out_function: static GList* l7vs_sched_wrr_serch_sutableRS( GList* list, int weight ) : return %p" , candidate );
+ }
+ return candidate;
+}