source/libnstd/linearhash.c

0001 /**
0002  * @brief Linear memory hashing routines (a.k.a Open Addressing with Linear Probing)
0003  *
0004  * @file linearhash.c
0005  */
0006 /* -----------------------------------------------------------------------------
0007  * Enduro/X Middleware Platform for Distributed Transaction Processing
0008  * Copyright (C) 2009-2016, ATR Baltic, Ltd. All Rights Reserved.
0009  * Copyright (C) 2017-2023, Mavimax, Ltd. All Rights Reserved.
0010  * This software is released under one of the following licenses:
0011  * AGPL (with Java and Go exceptions) or Mavimax's license for commercial use.
0012  * See LICENSE file for full text.
0013  * -----------------------------------------------------------------------------
0014  * AGPL license:
0015  *
0016  * This program is free software; you can redistribute it and/or modify it under
0017  * the terms of the GNU Affero General Public License, version 3 as published
0018  * by the Free Software Foundation;
0019  *
0020  * This program is distributed in the hope that it will be useful, but WITHOUT ANY
0021  * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A
0022  * PARTICULAR PURPOSE. See the GNU Affero General Public License, version 3
0023  * for more details.
0024  *
0025  * You should have received a copy of the GNU Affero General Public License along
0026  * with this program; if not, write to the Free Software Foundation, Inc.,
0027  * 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
0028  *
0029  * -----------------------------------------------------------------------------
0030  * A commercial use license is available from Mavimax, Ltd
0031  * contact@mavimax.com
0032  * -----------------------------------------------------------------------------
0033  */
0034 #include <ndrx_config.h>
0035 #include <string.h>
0036 #include <stdio.h>
0037 #include <stdlib.h>
0038 #include <memory.h>
0039 #include <time.h>
0040 #include <sys/time.h>
0041 #include <unistd.h>
0042 #include <stdarg.h>
0043 #include <arpa/inet.h>
0044 #include <errno.h>
0045 #include <fcntl.h>
0046
0047 #include <ndrstandard.h>
0048 #include <ndebug.h>
0049 #include <nstdutil.h>
0050 #include <sys_unix.h>
0051 #include <exsha1.h>
0052 #include <excrypto.h>
0053 #include <userlog.h>
0054 #include <expluginbase.h>
0055 #include <exaes.h>
0056 #include <exbase64.h>
0057
0058 /*---------------------------Externs------------------------------------*/
0059 /*---------------------------Macros-------------------------------------*/
0060 #define GET_FLAGS(CONF, IDX)  *((short*) ((*CONF->memptr) + (CONF->elmsz * IDX) + CONF->flags_offset))
0061
0062 #define NDRX_LH_ENT_NONE            0       /**< Linear hash entry not used */
0063 #define NDRX_LH_ENT_MATCH           1       /**< Linear hash entry matched  */
0064 #define NDRX_LH_ENT_OLD             2       /**< Linear hash entry was used */
0065
0066 /*---------------------------Enums--------------------------------------*/
0067 /*---------------------------Typedefs-----------------------------------*/
0068 /*---------------------------Globals------------------------------------*/
0069 /*---------------------------Statics------------------------------------*/
0070 /*---------------------------Prototypes---------------------------------*/
0071
0072 /**
0073  * Linear hash search routine.
0074  * NOTE, when installing value in hash NDRX_LH_FLAG_WASUSED must be always set.
0075  * Function is not thread safe (outside locking must be used)
0076  * @param conf hashing configuration
0077  * @param key_get key value to get
0078  * @param key_len key length (used where applicable)
0079  * @param oflag create flag (O_CREAT is checked)
0080  * @param pos output position
0081  * @param have_value EXTRUE -> Valid value is present, EXFALSE -> No valid value
0082  * @param key_typ key type msg
0083  * @return EXTRUE -> Position found (with valid or not valid value), POSITION not found
0084  *  either was not O_CREATE or if was, then hash is full
0085  */
0086 expublic int ndrx_lh_position_get(ndrx_lh_config_t *conf,
0087         void *key_get, size_t key_len,
0088         int oflag, int *pos, int *have_value, char *key_typ)
0089 {
0090     int ret=NDRX_LH_ENT_NONE;
0091     int try = EXFAIL;
0092     int start = try;
0093     int overflow = EXFALSE;
0094     int iterations = 0;
0095     char key_debug[256] = {EXEOS};
0096     char val_debug[256] = {EXEOS};
0097     short flags;
0098
0099     /* get debug key */
0100
0101     if (debug_get_ndrx_level()>=log_debug)
0102     {
0103         conf->p_key_debug(conf, key_get, key_len, key_debug, sizeof(key_debug));
0104     }
0105
0106     /*
0107      * 20/10/2018 Got to loop twice!!!!
0108      * Some definitions:
0109      * A - our Q
0110      * B - other Q
0111      *
0112      * The problem:
0113      * 1) B gets installed in our cell / direct hash number
0114      * 2) A gets installed in cell+1 index
0115      * 3) B gets uninstalled / cell becomes as stale
0116      * 4) A tries installed Q again, and it hits the cell and not the cell+1
0117      *
0118      * ----
0119      * Thus to solve this, we got to firstly perform "read only" lookup on the
0120      * queue tables to see, is queue already present there or not. And if not,
0121      * only then perform write to maps..
0122      *
0123      * !!!! Needs to check with the _ndrx_shm_get_svc() wouldn't be there the
0124      * same problem !!!!
0125      *
0126      */
0127     if (oflag & O_CREAT)
0128     {
0129         int try_read;
0130         int read_have_value;
0131
0132         if (ndrx_lh_position_get(conf, key_get, key_len, 0,
0133                 &try_read, &read_have_value, key_typ) && read_have_value)
0134         {
0135             try = try_read;
0136         }
0137     }
0138
0139     if (EXFAIL==try)
0140     {
0141         /*
0142         try = ndrx_hash_fn(pathname) % M_queuesmax;
0143          */
0144         try = conf->p_key_hash(conf, key_get, key_len);
0145     }
0146     else
0147     {
0148         NDRX_LOG(log_debug, "Got existing record at %d", try);
0149     }
0150
0151     start=try;
0152     *pos=EXFAIL;
0153
0154     NDRX_LOG(6, "Try key for [%s] is %d, shm is: %p oflag: %d",
0155                                         key_debug, try, *(conf->memptr), oflag);
0156     /*
0157      * So we loop over filled entries until we found empty one or
0158      * one which have been initialised by this service.
0159      *
0160      * So if there was overflow, then loop until the start item.
0161      */
0162     while (( (flags=GET_FLAGS(conf, try)) & NDRX_LH_FLAG_WASUSED)
0163             && (!overflow || (overflow && try < start)))
0164     {
0165 /*        if (0==strcmp(NDRX_SVQ_INDEX(svq, try)->qstr, pathname)) */
0166         if (0==conf->p_compare(conf, key_get, key_len, try))
0167         {
0168             *pos=try;
0169
0170             if (flags & NDRX_LH_FLAG_ISUSED)
0171             {
0172                 ret=NDRX_LH_ENT_MATCH;
0173             }
0174             else
0175             {
0176                 ret=NDRX_LH_ENT_OLD;
0177             }
0178
0179             break;  /* <<< Break! */
0180         }
0181
0182     if (oflag & O_CREAT)
0183     {
0184             if (!(flags & NDRX_LH_FLAG_ISUSED))
0185             {
0186                 /* found used position */
0187                 ret=NDRX_LH_ENT_OLD;
0188                 break; /* <<< break! */
0189             }
0190     }
0191
0192         try++;
0193
0194         /* we loop over...
0195          * Feature #139 mvitolin, 09/05/2017
0196          * Fix potential overflow issues at the border... of SHM...
0197          */
0198         if (try>=conf->elmmax)
0199         {
0200             try = 0;
0201             overflow=EXTRUE;
0202             NDRX_LOG(log_debug, "Overflow reached for search of [%s]", key_debug);
0203         }
0204         iterations++;
0205
0206         NDRX_LOG(log_debug, "Trying %d for [%s]", try, key_debug);
0207     }
0208
0209     *pos=try;
0210
0211     switch (ret)
0212     {
0213         case NDRX_LH_ENT_OLD:
0214             *have_value = EXFALSE;
0215             ret = EXTRUE;   /* have position */
0216             break;
0217         case NDRX_LH_ENT_NONE:
0218
0219                 /* if last one is not used, either we hit it first on empty hash
0220                  * or we started somewhere at the end, overflowed and hit
0221                  * an empty cell..
0222                  *  */
0223                 if (!(flags & NDRX_LH_FLAG_WASUSED))
0224                 {
0225                     *have_value = EXFALSE;
0226                     ret = EXTRUE;   /* has position */
0227                 }
0228                 else
0229                 {
0230                     *have_value = EXFALSE;
0231                     ret = EXFALSE;   /* no position */
0232                 }
0233
0234             break;
0235         case NDRX_LH_ENT_MATCH:
0236             *have_value = EXTRUE;
0237             ret = EXTRUE;   /* have position */
0238             break;
0239         default:
0240
0241             NDRX_LOG(log_error, "!!! should not get here...");
0242             break;
0243     }
0244
0245     /* get debug value */
0246     if (debug_get_ndrx_level()>=log_debug)
0247     {
0248         conf->p_val_debug(conf, try, val_debug, sizeof(val_debug));
0249     }
0250
0251     NDRX_LOG(6, "ndrx_lh_position_get %s [%s] - result: %d, "
0252                 "iterations: %d, pos: %d, have_value: %d flags: %hd [%s]",
0253                 key_typ, key_debug, ret, iterations, *pos, *have_value,
0254                 GET_FLAGS(conf, try), val_debug);
0255
0256     return ret;
0257 }
0258
0259
0260
0261 /* vim: set ts=4 sw=4 et smartindent: */