Changeset 2507 for trunk/src


Ignore:
Timestamp:
Jan 24, 2000, 2:45:21 AM (26 years ago)
Author:
bird
Message:

Heapcoding nearly completed...

Location:
trunk/src/win32k/misc
Files:
1 added
4 edited

Legend:

Unmodified
Added
Removed

  • trunk/src/win32k/misc/avl.c

    r2501 r2507  
    1 /* $Id: avl.c,v 1.2 2000-01-22 18:21:02 bird Exp $
     1/* $Id: avl.c,v 1.3 2000-01-24 01:45:19 bird Exp $
    22 *
    33 * AVL-Tree (lookalike) implementation.
    … …  
    436436    if (*ppTree != NULL)
    437437    {
    438         pEnumData->fFromLeft = fFromLeft;
     438        pEnumData->fFromLeft = (char)fFromLeft;
    439439        pEnumData->cEntries = 1;
    440440        pEnumData->aEntries[0] = *ppTree;

  • trunk/src/win32k/misc/heaptest.c

    r2503 r2507  
    1 /* $Id: heaptest.c,v 1.2 2000-01-23 03:20:52 bird Exp $
     1/* $Id: heaptest.c,v 1.3 2000-01-24 01:45:20 bird Exp $
    22 *
    33 * Test of resident and swappable heaps.
    … …  
    1313*   Defined Constants
    1414*******************************************************************************/
    15 #define NUMBER_OF_POINTERS      16384
     15#define NUMBER_OF_POINTERS      1024
    1616#define RANDOMTEST_ITERATIONS   65536*2
    1717#define Int3()          __interrupt(3)
    … …  
    2121*   Internal Functions
    2222*******************************************************************************/
    23 #include "malloc.h"
     23/*#include "malloc.h"*/
    2424#include "rmalloc.h"
     25#include "smalloc.h"
    2526#include "macros.h"
    2627#include <stdio.h>
    … …  
    4243    unsigned      crealloc;
    4344    int           i;
     45    int           fResTests = 0;
     46    int           fResSimple = 0;
     47    int           fResRandom = 0;
     48    int           fSwpTests = 1;
     49    int           fSwpSimple = 1;
     50    int           fSwpRandom = 1;
    4451
    4552    /*
    4653     * Initiate the heap.
    4754     */
    48     if (ResHeapInit(128*1024, 1024*1024*64) != 0)
     55    if (resHeapInit(128*1024, 1024*1024*64) != 0)
    4956    {
    5057        printf("Failed to initiate the resident heap.\n");
    … …  
    5259    }
    5360
    54 /*
    55  *
    56  * resident heap tests
    57  * resident heap tests
    58  *
    59  */
    60 #if 1
    61     /*
    62      * Simple allocation test.
    63      */
    64     for (i = 0; i < NUMBER_OF_POINTERS; i++)
     61    if (swpHeapInit(128*1024, 1024*1024*64) != 0)
    6562    {
    66         do
     63        printf("Failed to initiate the swappable heap.\n");
     64        return 2;
     65    }
     66
     67
     68
     69    if (fResTests)
     70    {
     71        /*
     72         *
     73         * resident heap tests
     74         * resident heap tests
     75         *
     76         */
     77        if (fResSimple)
    6778        {
    68             acb[i] = rand();
    69         } while(acb[i] == 0 || acb[i] > 127);
    70 
    71         if ((i % (NUMBER_OF_POINTERS/3)) == 1)
    72             acb[i] += 1024*260;
    73         apv[i] = rmalloc(acb[i]);
    74         if (apv[i] == NULL)
    75         {
    76             printf("rmalloc failed: acb[%d]=%d\n", i, acb[i]);
    77             if (acb[i] > 1000)
    78                 break;
    79         }
    80         memset(apv[i], 0xA, MIN(acb[i],16));
    81         cb += acb[i];
    82     }
    83 
    84     printf("Finished allocating memory: %d allocations  %d bytes\n", i, cb);
    85 
    86 
    87     printf("_res_dump_subheaps:\n");
    88     _res_dump_subheaps();
    89 
    90     for (i = 0; i < NUMBER_OF_POINTERS; i++)
    91     {
    92         int cb = _res_msize(apv[i]);
    93         if (cb != ((acb[i] + 3) & ~3) && (cb < ((acb[i] + 3) & ~3) || cb > 52 + ((acb[i] + 3) & ~3)) )
    94             printf("size of avp[%d] (%d) != acb[%] (%d)\n", i, cb, i, acb[i]);
    95         rfree(apv[i]);
    96     }
    97 
    98 
    99     /*
    100      * test _res_heapmin
    101      */
    102     printf("_res_memfree - before heapmin: %d\n", _res_memfree());
    103     _res_heapmin();
    104     printf("_res_memfree - after heapmin : %d\n", _res_memfree());
    105 
    106     /*
    107      * Test _res_dump_subheaps
    108      */
    109     printf("\n_res_dump_subheaps:\n");
    110     _res_dump_subheaps();
    111 #endif
    112 
    113 
    114     /*
    115      * Test 2 - random allocation and freeing of memory.
    116      */
    117     printf("\n"
    118            "Random allocation and freeing test:\n");
    119     for (i = 0; i < NUMBER_OF_POINTERS; i++)
    120         apv[i] = NULL, acb[i] = 0;
    121     cAllocations = 0;
    122     i = 0;
    123     cb = 0;
    124     crfree = 0;
    125     crmalloc = 0;
    126     crealloc = 0;
    127     while (i++ < RANDOMTEST_ITERATIONS || cAllocations > 0)
    128     {
    129         int j;
    130         j = rand();
    131         if (cAllocations + (NUMBER_OF_POINTERS/20) < NUMBER_OF_POINTERS &&
    132             (i < RANDOMTEST_ITERATIONS*1/4 ? (j % 8) > 2 :
    133              i < RANDOMTEST_ITERATIONS*2/4 ? (j % 8) > 3 :
    134              i < RANDOMTEST_ITERATIONS*3/4 ? (j % 8) > 4 :
    135              i < RANDOMTEST_ITERATIONS     ? (j % 8) > 5 : 0
    136              )
    137             )
    138         {   /* malloc */
    139             for (j = 0; j < NUMBER_OF_POINTERS && apv[j] != NULL; j++)
    140                 (void)0;
    141             if (j < NUMBER_OF_POINTERS)
     79            /*
     80             * Simple allocation test.
     81             */
     82            for (i = 0; i < NUMBER_OF_POINTERS; i++)
    14283            {
    14384                do
    14485                {
    145                     acb[j] = rand();
    146                 } while (acb[j] == 0 || (acb[j] > 2048 && (i % 11) != 10));
    147                 if ((i % (RANDOMTEST_ITERATIONS/20)) == 1)
    148                     acb[j] += 1024*256;
    149                 apv[j] = rmalloc(acb[j]);
    150                 if (apv[j] == NULL)
     86                    acb[i] = rand();
     87                } while(acb[i] == 0 || acb[i] > 127);
     88
     89                if ((i % (NUMBER_OF_POINTERS/3)) == 1)
     90                    acb[i] += 1024*260;
     91                apv[i] = rmalloc(acb[i]);
     92                if (apv[i] == NULL)
    15193                {
    152                     printf("rmalloc failed, acb[%d] = %d\n", j, acb[j]);
    153                     if (acb[j] > 10000)
     94                    printf("rmalloc failed: acb[%d]=%d\n", i, acb[i]);
     95                    if (acb[i] > 1000)
     96                        break;
     97                }
     98                memset(apv[i], 0xA, MIN(acb[i],16));
     99                cb += acb[i];
     100            }
     101
     102            printf("Finished allocating memory: %d allocations  %d bytes\n", i, cb);
     103
     104
     105            printf("_res_dump_subheaps:\n");
     106            _res_dump_subheaps();
     107
     108            for (i = 0; i < NUMBER_OF_POINTERS; i++)
     109            {
     110                int cb = _res_msize(apv[i]);
     111                if (cb != ((acb[i] + 3) & ~3) && (cb < ((acb[i] + 3) & ~3) || cb > 52 + ((acb[i] + 3) & ~3)) )
     112                    printf("size of avp[%d] (%d) != acb[%d] (%d)\n", i, cb, i, acb[i]);
     113                rfree(apv[i]);
     114            }
     115
     116
     117            /*
     118             * test _res_heapmin
     119             */
     120            printf("_res_memfree - before heapmin: %d\n", _res_memfree());
     121            _res_heapmin();
     122            printf("_res_memfree - after heapmin : %d\n", _res_memfree());
     123
     124            /*
     125             * Test _res_dump_subheaps
     126             */
     127            printf("\n_res_dump_subheaps:\n");
     128            _res_dump_subheaps();
     129        } /* fResSimple */
     130
     131
     132        if (fResRandom)
     133        {
     134            /*
     135             * Test 2 - random allocation and freeing of memory.
     136             */
     137            printf("\n"
     138                   "Random allocation and freeing test:\n");
     139            for (i = 0; i < NUMBER_OF_POINTERS; i++)
     140                apv[i] = NULL, acb[i] = 0;
     141            cAllocations = 0;
     142            i = 0;
     143            cb = 0;
     144            crfree = 0;
     145            crmalloc = 0;
     146            crealloc = 0;
     147            while (i++ < RANDOMTEST_ITERATIONS || cAllocations > 0)
     148            {
     149                int j;
     150                j = rand();
     151                if (cAllocations + (NUMBER_OF_POINTERS/20) < NUMBER_OF_POINTERS &&
     152                    (i < RANDOMTEST_ITERATIONS*1/4 ? (j % 8) > 4 :
     153                     i < RANDOMTEST_ITERATIONS*2/4 ? (j % 8) > 5 :
     154                     i < RANDOMTEST_ITERATIONS*3/4 ? (j % 8) > 6 :
     155                     i < RANDOMTEST_ITERATIONS     ? (j % 8) > 6 : 0
     156                     )
     157                    )
     158                {   /* malloc */
     159                    for (j = 0; j < NUMBER_OF_POINTERS && apv[j] != NULL; j++)
     160                        (void)0;
     161                    if (j < NUMBER_OF_POINTERS)
     162                    {
     163                        do
     164                        {
     165                            acb[j] = rand();
     166                        } while (acb[j] == 0 || (acb[j] > 2048 && (i % 11) != 10));
     167                        if ((i % (RANDOMTEST_ITERATIONS/20)) == 1)
     168                            acb[j] += 1024*256;
     169                        apv[j] = rmalloc(acb[j]);
     170                        if (apv[j] == NULL)
     171                        {
     172                            printf("rmalloc failed, acb[%d] = %d\n", j, acb[j]);
     173                            if (acb[j] > 10000)
     174                                continue;
     175                            break;
     176                        }
     177                        memset(apv[j], 0xA, MIN(acb[j],16));
     178                        cAllocations++;
     179                        cb += acb[j];
     180                        crmalloc++;
     181                    }
     182                }
     183                else
     184                { /* free or realloc */
     185                    if (cAllocations == 0)
    154186                        continue;
    155                     break;
    156                 }
    157                 memset(apv[j], 0xA, MIN(acb[j],16));
    158                 cAllocations++;
    159                 cb += acb[j];
    160                 crmalloc++;
    161             }
    162         }
    163         else
    164         { /* free or realloc */
    165             if (cAllocations == 0)
    166                 continue;
    167 
    168             if (cAllocations < NUMBER_OF_POINTERS/10)
    169             {
    170                 for (j = 0; j < NUMBER_OF_POINTERS && apv[j] == NULL; j++)
    171                     (void)0;
    172             }
    173             else
    174             {
    175                 int k = 0;
     187
     188                    if (cAllocations < NUMBER_OF_POINTERS/10)
     189                    {
     190                        for (j = 0; j < NUMBER_OF_POINTERS && apv[j] == NULL; j++)
     191                            (void)0;
     192                    }
     193                    else
     194                    {
     195                        int k = 0;
     196                        do
     197                        {
     198                            j = rand();
     199                        } while (k++ < NUMBER_OF_POINTERS/2 && (j >= NUMBER_OF_POINTERS || apv[j] == NULL));
     200                        if (k >= NUMBER_OF_POINTERS/2)
     201                        {
     202                            for (j = 0; j < NUMBER_OF_POINTERS && apv[j] == NULL; j++)
     203                                (void)0;
     204                        }
     205                    }
     206
     207                    if (j < NUMBER_OF_POINTERS && apv[j] != NULL)
     208                    {
     209                        int cb = _res_msize(apv[j]);
     210                        if (cb != ((acb[j] + 3) & ~3) && (cb < ((acb[j] + 3) & ~3) || cb > 52 + ((acb[j] + 3) & ~3)) )
     211                            printf("size of avp[%d] (%d) != acb[%d] (%d)\n", j, cb, j, acb[j]);
     212                        if (i < RANDOMTEST_ITERATIONS*3/4 && j % 3 == 0)
     213                        {   /* realloc */
     214                            int cb;
     215                            void *pv;
     216                            crealloc++;
     217                            do
     218                            {
     219                                cb = rand();
     220                            } while (cb == 0 || cb > 3072);
     221                            /*
     222                            if (i >= 0x1c14)
     223                                Int3();
     224                            */
     225                            pv = rrealloc(apv[j], cb);
     226                            if (pv == NULL)
     227                            {
     228                                printf("realloc(apv[%d](0x%08), %d) failed\n", j, apv[j], cb);
     229                                continue;
     230                            }
     231                            apv[j] = pv;
     232                            acb[j] = cb;
     233                        }
     234                        else
     235                        {   /* free */
     236                            rfree(apv[j]);
     237                            apv[j] = NULL;
     238                            cAllocations--;
     239                            crfree++;
     240                        }
     241                    }
     242                }
     243                _res_heap_check();
     244                if (RANDOMTEST_ITERATIONS/2 == i)
     245                    _res_dump_subheaps();
     246                if ((i % 2048) == 0)
     247                    printf("i=%d cAllocations=%d\n", i, cAllocations);
     248            }
     249
     250            printf("cb=%d crfree=%d crmalloc=%d crealloc=%d\n", cb, crfree, crmalloc, crealloc);
     251
     252            printf("_res_dump_subheaps:\n");
     253            _res_dump_subheaps();
     254
     255            printf("_res_memfree - before heapmin: %d\n", _res_memfree());
     256            _res_heapmin();
     257            printf("_res_memfree - after heapmin : %d\n", _res_memfree());
     258
     259            printf("_res_dump_subheaps:\n");
     260            _res_dump_subheaps();
     261        } /* fResRandom */
     262    } /* fResTests */
     263
     264
     265/*
     266 *
     267 * swappable heap tests
     268 * swappable heap tests
     269 *
     270 */
     271    if (fSwpTests)
     272    {
     273        if (fSwpSimple)
     274        {
     275            /*
     276             * Simple allocation test.
     277             */
     278            for (i = 0; i < NUMBER_OF_POINTERS; i++)
     279            {
    176280                do
    177281                {
    178                     j = rand();
    179                 } while (k++ < NUMBER_OF_POINTERS/2 && (j >= NUMBER_OF_POINTERS || apv[j] == NULL));
    180                 if (k >= NUMBER_OF_POINTERS/2)
     282                    acb[i] = rand();
     283                } while(acb[i] == 0 || acb[i] > 127);
     284
     285                if ((i % (NUMBER_OF_POINTERS/3)) == 1)
     286                    acb[i] += 1024*260;
     287                apv[i] = smalloc(acb[i]);
     288                if (apv[i] == NULL)
    181289                {
    182                     for (j = 0; j < NUMBER_OF_POINTERS && apv[j] == NULL; j++)
     290                    printf("smalloc failed: acb[%d]=%d\n", i, acb[i]);
     291                    if (acb[i] > 1000)
     292                        break;
     293                }
     294                memset(apv[i], 0xA, MIN(acb[i],16));
     295                cb += acb[i];
     296            }
     297
     298            printf("Finished allocating memory: %d allocations  %d bytes\n", i, cb);
     299
     300
     301            printf("_swp_dump_subheaps:\n");
     302            _swp_dump_subheaps();
     303
     304            for (i = 0; i < NUMBER_OF_POINTERS; i++)
     305            {
     306                int cb = _swp_msize(apv[i]);
     307                if (cb != ((acb[i] + 3) & ~3) && (cb < ((acb[i] + 3) & ~3) || cb > 52 + ((acb[i] + 3) & ~3)) )
     308                    printf("size of avp[%d] (%d) != acb[%d] (%d)\n", i, cb, i, acb[i]);
     309                sfree(apv[i]);
     310            }
     311
     312
     313            /*
     314             * test _swp_heapmin
     315             */
     316            printf("_swp_memfree - before heapmin: %d\n", _swp_memfree());
     317            _swp_heapmin();
     318            printf("_swp_memfree - after heapmin : %d\n", _swp_memfree());
     319
     320            /*
     321             * Test _swp_dump_subheaps
     322             */
     323            printf("\n_swp_dump_subheaps:\n");
     324            _swp_dump_subheaps();
     325        } /* fSwpSimple */
     326
     327
     328        if (fSwpRandom)
     329        {
     330            /*
     331             * Test 2 - random allocation and freeing of memory.
     332             */
     333            printf("\n"
     334                   "Random allocation and freeing test:\n");
     335            for (i = 0; i < NUMBER_OF_POINTERS; i++)
     336                apv[i] = NULL, acb[i] = 0;
     337            cAllocations = 0;
     338            i = 0;
     339            cb = 0;
     340            crfree = 0;
     341            crmalloc = 0;
     342            crealloc = 0;
     343            while (i++ < RANDOMTEST_ITERATIONS || cAllocations > 0)
     344            {
     345                int j;
     346                j = rand();
     347                if (cAllocations + (NUMBER_OF_POINTERS/20) < NUMBER_OF_POINTERS &&
     348                    (i < RANDOMTEST_ITERATIONS*1/4 ? (j % 8) > 4 :
     349                     i < RANDOMTEST_ITERATIONS*2/4 ? (j % 8) > 5 :
     350                     i < RANDOMTEST_ITERATIONS*3/4 ? (j % 8) > 6 :
     351                     i < RANDOMTEST_ITERATIONS     ? (j % 8) > 6 : 0
     352                     )
     353                    )
     354                {   /* malloc */
     355                    for (j = 0; j < NUMBER_OF_POINTERS && apv[j] != NULL; j++)
    183356                        (void)0;
    184                 }
    185             }
    186 
    187             if (j < NUMBER_OF_POINTERS && apv[j] != NULL)
    188             {
    189                 int cb = _res_msize(apv[j]);
    190                 if (cb != ((acb[j] + 3) & ~3) && (cb < ((acb[j] + 3) & ~3) || cb > 52 + ((acb[j] + 3) & ~3)) )
    191                     printf("size of avp[%d] (%d) != acb[%d] (%d)\n", j, cb, j, acb[j]);
    192                 if (i < RANDOMTEST_ITERATIONS*3/4 && j % 3 == 0)
    193                 {   /* realloc */
    194                     int cb;
    195                     void *pv;
    196                     crealloc++;
    197                     do
    198                     {
    199                         cb = rand();
    200                     } while (cb == 0 || cb > 3072);
    201                     /*
    202                     if (i >= 0x1c14)
    203                         Int3();
    204                     */
    205                     pv = rrealloc(apv[j], cb);
    206                     if (pv == NULL)
    207                     {
    208                         printf("realloc(apv[%d](0x%08), %d) failed\n", j, apv[j], cb);
     357                    if (j < NUMBER_OF_POINTERS)
     358                    {
     359                        do
     360                        {
     361                            acb[j] = rand();
     362                        } while (acb[j] == 0 || (acb[j] > 2048 && (i % 11) != 10));
     363                        if ((i % (RANDOMTEST_ITERATIONS/20)) == 1)
     364                            acb[j] += 1024*256;
     365                        apv[j] = smalloc(acb[j]);
     366                        if (apv[j] == NULL)
     367                        {
     368                            printf("rmalloc failed, acb[%d] = %d\n", j, acb[j]);
     369                            if (acb[j] > 10000)
     370                                continue;
     371                            break;
     372                        }
     373                        memset(apv[j], 0xA, MIN(acb[j],16));
     374                        cAllocations++;
     375                        cb += acb[j];
     376                        crmalloc++;
     377                    }
     378                }
     379                else
     380                { /* free or realloc */
     381                    if (cAllocations == 0)
    209382                        continue;
    210                     }
    211                     apv[j] = pv;
    212                     acb[j] = cb;
    213                 }
    214                 else
    215                 {   /* free */
    216                     rfree(apv[j]);
    217                     apv[j] = NULL;
    218                     cAllocations--;
    219                     crfree++;
    220                 }
    221             }
    222         }
    223         /*_res_heap_check();*/
    224         if (RANDOMTEST_ITERATIONS/2 == i)
    225             _res_dump_subheaps();
    226         if ((i % 2048) == 0)
    227             printf("i=%d cAllocations=%d\n", i, cAllocations);
     383
     384                    if (cAllocations < NUMBER_OF_POINTERS/10)
     385                    {
     386                        for (j = 0; j < NUMBER_OF_POINTERS && apv[j] == NULL; j++)
     387                            (void)0;
     388                    }
     389                    else
     390                    {
     391                        int k = 0;
     392                        do
     393                        {
     394                            j = rand();
     395                        } while (k++ < NUMBER_OF_POINTERS/2 && (j >= NUMBER_OF_POINTERS || apv[j] == NULL));
     396                        if (k >= NUMBER_OF_POINTERS/2)
     397                        {
     398                            for (j = 0; j < NUMBER_OF_POINTERS && apv[j] == NULL; j++)
     399                                (void)0;
     400                        }
     401                    }
     402
     403                    if (j < NUMBER_OF_POINTERS && apv[j] != NULL)
     404                    {
     405                        int cb = _swp_msize(apv[j]);
     406                        if (cb != ((acb[j] + 3) & ~3) && (cb < ((acb[j] + 3) & ~3) || cb > 52 + ((acb[j] + 3) & ~3)) )
     407                            printf("size of avp[%d] (%d) != acb[%d] (%d)\n", j, cb, j, acb[j]);
     408                        if (i < RANDOMTEST_ITERATIONS*3/4 && j % 3 == 0)
     409                        {   /* realloc */
     410                            int cb;
     411                            void *pv;
     412                            crealloc++;
     413                            do
     414                            {
     415                                cb = rand();
     416                            } while (cb == 0 || cb > 3072);
     417                            /*
     418                            if (i >= 0x1c14)
     419                                Int3();
     420                            */
     421                            pv = srealloc(apv[j], cb);
     422                            if (pv == NULL)
     423                            {
     424                                printf("realloc(apv[%d](0x%08), %d) failed\n", j, apv[j], cb);
     425                                continue;
     426                            }
     427                            apv[j] = pv;
     428                            acb[j] = cb;
     429                        }
     430                        else
     431                        {   /* free */
     432                            sfree(apv[j]);
     433                            apv[j] = NULL;
     434                            cAllocations--;
     435                            crfree++;
     436                        }
     437                    }
     438                }
     439                _swp_heap_check();
     440                if (RANDOMTEST_ITERATIONS/2 == i)
     441                    _swp_dump_subheaps();
     442                if ((i % 2048) == 0)
     443                    printf("i=%d cAllocations=%d\n", i, cAllocations);
     444            }
     445
     446            printf("cb=%d crfree=%d crmalloc=%d crealloc=%d\n", cb, crfree, crmalloc, crealloc);
     447
     448            printf("_swp_dump_subheaps:\n");
     449            _swp_dump_subheaps();
     450
     451            printf("_swp_memfree - before heapmin: %d\n", _swp_memfree());
     452            _swp_heapmin();
     453            printf("_swp_memfree - after heapmin : %d\n", _swp_memfree());
     454
     455            printf("_swp_dump_subheaps:\n");
     456            _swp_dump_subheaps();
     457        } /* fSwpRandom */
    228458    }
    229 
    230     printf("cb=%d crfree=%d crmalloc=%d crealloc=%d\n", cb, crfree, crmalloc, crealloc);
    231 
    232     printf("_res_dump_subheaps:\n");
    233     _res_dump_subheaps();
    234 
    235     printf("_res_memfree - before heapmin: %d\n", _res_memfree());
    236     _res_heapmin();
    237     printf("_res_memfree - after heapmin : %d\n", _res_memfree());
    238 
    239     printf("_res_dump_subheaps:\n");
    240     _res_dump_subheaps();
    241 
    242 
    243 
    244 /*
    245  *
    246  * swappable heap tests
    247  * swappable heap tests
    248  *
    249  */
    250 
    251459
    252460

  • trunk/src/win32k/misc/rmalloc.c

    r2503 r2507  
    1 /* $Id: rmalloc.c,v 1.2 2000-01-23 03:20:53 bird Exp $
     1/* $Id: rmalloc.c,v 1.3 2000-01-24 01:45:20 bird Exp $
    22 *
    33 * Resident Heap.
    … …  
    66 *       Use with care! We're running at Ring-0!
    77 *
    8  * Copyright (c) 1999 knut st. osmundsen
     8 * Copyright (c) 1999-2000 knut st. osmundsen
    99 *
    1010 * Project Odin Software License can be found in LICENSE.TXT
    … …  
    434434 * @param     cbSizeMax   Maximum heapsize in bytes.
    435435 */
    436 int ResHeapInit(unsigned cbSizeInit, unsigned cbSizeMax)
     436int resHeapInit(unsigned cbSizeInit, unsigned cbSizeMax)
    437437{
    438438    unsigned cbSize = MAX(BLOCKSIZE, cbSizeInit);

  • trunk/src/win32k/misc/rmalloc_avl.c

    r2503 r2507  
    1 /* $Id: rmalloc_avl.c,v 1.2 2000-01-23 03:20:53 bird Exp $
     1/* $Id: rmalloc_avl.c,v 1.3 2000-01-24 01:45:20 bird Exp $
    22 *
    33 * Resident Heap - AVL.
    … …  
    66 *       Use with care! We're running at Ring-0!
    77 *
    8  * Copyright (c) 1999 knut st. osmundsen
     8 * Copyright (c) 1999-2000 knut st. osmundsen
    99 *
    1010 * Project Odin Software License can be found in LICENSE.TXT
    … …  
    1212 */
    1313
    14 #define static
     14
    1515/*******************************************************************************
    1616*   Defined Constants And Macros                                               *
    … …  
    1818#ifdef DEBUG
    1919    #define DEBUG_ALLOC
    20     #undef ALLWAYS_HEAPCHECK
     20    #define ALLWAYS_HEAPCHECK
    2121#endif
    2222
    … …  
    167167    PMEMBLOCKFREE pmbfTmp;
    168168
    169     pmbfTmp = (PMEMBLOCKFREE)AVLGetWithParent((PPAVLNODECORE)&pha->pcoreFreeSize,
     169    pmbfTmp = (PMEMBLOCKFREE)AVLGetWithParent(&pha->pcoreFreeSize,
    170170                                              (PPAVLNODECORE)SSToDS(&pmbfParent),
    171171                                              pmbf->coreFree.Key);
    … …  
    191191            if (pmbfTmp->pmbfNext == NULL)
    192192            {   /* no list - no other nodes of this size: simply remove it. */
    193                 AVLRemove((PPAVLNODECORE)&pha->pcoreFreeSize, pmbf->coreFree.Key);
     193                AVLRemove(&pha->pcoreFreeSize, pmbf->coreFree.Key);
    194194            }
    195195            else
    … …  
    200200                    pmbfParent = MEMBLOCKFREE_FROM_FREESIZENODE(pmbfParent);
    201201                    if (pmbfTmp->coreFree.Key < pmbfParent->coreFree.Key)
    202                         pmbfParent->coreFree.pLeft = (PAVLNODECORE)&pmbf->pmbfNext->coreFree;
     202                        pmbfParent->coreFree.pLeft = &pmbf->pmbfNext->coreFree;
    203203                    else
    204                         pmbfParent->coreFree.pRight = (PAVLNODECORE)&pmbf->pmbfNext->coreFree;
     204                        pmbfParent->coreFree.pRight = &pmbf->pmbfNext->coreFree;
    205205                }
    206206                else
    207                     pha->pcoreFreeSize = (PAVLNODECORE)&pmbf->pmbfNext->coreFree;
     207                    pha->pcoreFreeSize = &pmbf->pmbfNext->coreFree;
    208208            }
    209209        }
    … …  
    221221    PMEMBLOCKFREE pmbfTmp;
    222222
    223     pmbfTmp = (PMEMBLOCKFREE)AVLGet((PPAVLNODECORE)&pha->pcoreFreeSize, pmbf->coreFree.Key);
     223    pmbfTmp = (PMEMBLOCKFREE)AVLGet(&pha->pcoreFreeSize, pmbf->coreFree.Key);
    224224    if (pmbfTmp != NULL)
    225225    {
    … …  
    234234    {
    235235        pmbf->pmbfNext = NULL;
    236         AVLInsert((PPAVLNODECORE)&pha->pcoreFreeSize, &pmbf->coreFree);
     236        AVLInsert(&pha->pcoreFreeSize, &pmbf->coreFree);
    237237    }
    238238}
    … …  
    248248static void resInsertFree(PHEAPANCHOR pha, PMEMBLOCK pmb)
    249249{
    250     /* some more work left here... */
    251250    PMEMBLOCKFREE   pmbf = (PMEMBLOCKFREE)pmb;
    252251    PMEMBLOCKFREE   pmbfRight;
    … …  
    401400            register PHEAPANCHOR pha = *ppha;
    402401            PMEMBLOCK pmb;
     402            memset(pha, 0, sizeof(*pha));
    403403
    404404            /* anchor block */
    … …  
    407407            #endif
    408408            pha->cbSize = cbBlockSize;
    409             pha->pmbUsed = NULL;
    410             pha->cbUsed = 0;
    411             pha->cbFree = 0;
    412             pha->pcoreFreeSize = NULL;
    413409
    414410            /* free memblock */
    … …  
    458454 *                       NULL is allowed.
    459455 * @param     pvUser     User pointer to find the block to.
    460  * @param     fWithin    When this flag is set, the pointer may point anywhere within the block.
    461  *                       When clear, it has to point exactly at the start of the user data area.
    462456 */
    463457static PMEMBLOCK resFindUsedBlock(PHEAPANCHOR *ppha, void *pvUser)
    464458{
    465     if (pvUser != NULL && ppha != NULL)
     459    if (pvUser != NULL)
    466460    {
    467461        register PHEAPANCHOR pha = phaFirst;
    … …  
    524518            if (pha->ulSignature != HEAPANCHOR_SIGNATURE)
    525519            {
    526                 kprintf(("resFindUsedBlock: Invalid heapanchor signature.\n"));
     520                kprintf(("resFindWithinUsedBlock: Invalid heapanchor signature.\n"));
    527521                return NULL;
    528522            }
    … …  
    534528        if (pmb != NULL
    535529            && (unsigned)pmb + pmb->cbSize + CB_HDR > (unsigned)pvUser
    536             && (unsigned)pmb + CB_HDR >= (unsigned)pvUser
     530            && (unsigned)pmb + CB_HDR <= (unsigned)pvUser
    537531            )
    538532        {
    … …  
    558552 * @param     cbSizeMax   Maximum heapsize in bytes.
    559553 */
    560 int ResHeapInit(unsigned cbSizeInit, unsigned cbSizeMax)
     554int resHeapInit(unsigned cbSizeInit, unsigned cbSizeMax)
    561555{
    562556    unsigned  cbSize = MAX(BLOCKSIZE, cbSizeInit);
    … …  
    600594    #ifdef ALLWAYS_HEAPCHECK
    601595        if (!_res_heap_check())
    602         {
    603             /* error! */
    604             kprintf(("%s: _res_heap_check failed!\n", "heapInit"));
     596        {   /* error! */
     597            kprintf(("resHeapInit: _res_heap_check failed!\n"));
     598            #ifdef DEBUG
    605599            Int3();
     600            #endif
    606601            return -2;
    607602        }
    … …  
    623618void * rmalloc(unsigned cbSize)
    624619{
    625     void *pvRet = NULL;
    626 
    627620    #ifdef ALLWAYS_HEAPCHECK
    628         if (!_res_heap_check())
    629         {
    630             kprintf(("rmalloc: _res_heap_check failed!\n"));
    631             return NULL;
    632         }
     621    if (!_res_heap_check())
     622    {
     623        kprintf(("rmalloc: _res_heap_check failed!\n"));
     624        return NULL;
     625    }
    633626    #endif
    634627
    … …  
    640633        {
    641634            resInsertUsed(pha, pmb);
    642             pvRet = &pmb->achUserData[0];
     635            return &pmb->achUserData[0];
    643636        }
    644637    }
    645638    else
    646     {   /* error! */
    647639        kprintf(("rmalloc: error cbSize = 0\n"));
    648     }
    649 
    650     return pvRet;
     640
     641    return NULL;
    651642}
    652643
    … …  
    665656
    666657    #ifdef ALLWAYS_HEAPCHECK
    667         if (!_res_heap_check())
    668         {
    669             kprintf(("rmalloc: _res_heap_check failed!\n"));
    670             return NULL;
    671         }
     658    if (!_res_heap_check())
     659    {
     660        kprintf(("rrealloc: _res_heap_check failed!\n"));
     661        return NULL;
     662    }
    672663    #endif
    673664    pmb = resFindUsedBlock(SSToDS(&pha), pv);
    … …  
    684675                PMEMBLOCKFREE pmbfNew = (PMEMBLOCKFREE)((unsigned)pmb + CB_HDR + cbNew);
    685676                #ifdef DEBUG_ALLOC
    686                     pmbfNew->ulSignature = MEMBLOCK_SIGNATURE;
     677                pmbfNew->ulSignature = MEMBLOCK_SIGNATURE;
    687678                #endif
    688679                pha->cbUsed -= pmb->cbSize - cbNew;
    … …  
    691682                resInsertFree(pha, (PMEMBLOCK)pmbfNew);
    692683                #ifdef ALLWAYS_HEAPCHECK
    693                     if (!_res_heap_check())
     684                if (!_res_heap_check())
     685                {
     686                    kprintf(("rrealloc: _res_heap_check failed!\n"));
     687                    return NULL;
     688                }
     689                #endif
     690            }
     691        }
     692        else
     693        {   /* expand block - this code may be optimized... */
     694            #if 0
     695            pvRet = rmalloc(cbNew);
     696            if (pvRet != NULL)
     697            {
     698                memcpy(pvRet, pv, pmb->cbSize);
     699                rfree(pv);
     700            }
     701            #else
     702            /* optimized FIXME! */
     703            PMEMBLOCKFREE pmbfRightParent;
     704            PMEMBLOCKFREE pmbfRight = (PMEMBLOCKFREE)AVLGetWithParent((PPAVLNODECORE)&pha->pmbFree,
     705                                                                      (PPAVLNODECORE)SSToDS(&pmbfRightParent),
     706                                                                      (AVLKEY)PNEXT_BLOCK(pmb));
     707            if (pmbfRight != NULL && pmbfRight->coreFree.Key + pmb->cbSize + CB_HDR >= cbNew)
     708            {
     709                pvRet = pv;
     710                /* split the free block? */
     711                if (pmbfRight->coreFree.Key + pmb->cbSize + CB_HDR - sizeof(MEMBLOCKFREE) >= cbNew)
     712                {
     713                    unsigned      cb = pmbfRight->coreFree.Key;
     714                    PMEMBLOCKFREE pmbfNew = (PMEMBLOCKFREE)((unsigned)pmb + CB_HDR + cbNew);
     715                    resRemoveFromFreeSize(pha, pmbfRight);
     716                    pmbfNew->coreFree.Key = cb + pmb->cbSize - cbNew;
     717                    memmove((void*)&pmbfNew->core, (void*)&pmbfRight->core, sizeof(pmbfNew->core));
     718                    pmbfNew->core.Key = (AVLKEY)pmbfNew;
     719                    #ifdef DEBUG_ALLOC
     720                    pmbfNew->ulSignature = MEMBLOCK_SIGNATURE;
     721                    #endif
     722                    if (pmbfRightParent != NULL)
    694723                    {
    695                         kprintf(("rrealloc: _res_heap_check failed!\n"));
     724                        if (pmbfNew < pmbfRightParent)
     725                            pmbfRightParent->core.pLeft = &pmbfNew->core;
     726                        else
     727                            pmbfRightParent->core.pRight = &pmbfNew->core;
     728                    }
     729                    else
     730                        pha->pmbFree = (PMEMBLOCK)pmbfNew;
     731
     732                    resInsertIntoFreeSize(pha, pmbfNew);
     733                    pha->cbUsed += cbNew - pmb->cbSize;
     734                    pha->cbFree -= cb - pmbfNew->coreFree.Key;
     735                    pmb->cbSize = cbNew;
     736                }
     737                else
     738                {
     739                    if (AVLRemove((PPAVLNODECORE)&pha->pmbFree, (AVLKEY)pmbfRight) != (PAVLNODECORE)pmbfRight)
     740                    {
     741                        kprintf(("rrealloc: AVLRemove failed for pmbfRight - hmm!\n"));
    696742                        return NULL;
    697743                    }
    698                 #endif
     744                    resRemoveFromFreeSize(pha, pmbfRight);
     745                    pmb->cbSize += pmbfRight->coreFree.Key + CB_HDR;
     746                    pha->cbFree -= pmbfRight->coreFree.Key;
     747                    pha->cbUsed += pmbfRight->coreFree.Key + CB_HDR;
     748                }
     749
    699750            }
    700         }
    701         else
    702         {   /* expand block - this code may be more optimized... */
    703             #if 1
     751            else
     752            {   /* worst case: allocate a new block, copy data and free the old block. */
    704753                pvRet = rmalloc(cbNew);
    705754                if (pvRet != NULL)
    … …  
    708757                    rfree(pv);
    709758                }
    710             #else
    711                 /* optimized */
    712                 PMEMBLOCK pmb
     759            }
    713760            #endif
    714761        }
    … …  
    779826    #ifdef ALLWAYS_HEAPCHECK
    780827        if (!_res_heap_check())
    781             kprintf(("_msize: _res_heap_check failed!\n"));
     828            kprintf(("_res_msize: _res_heap_check failed!\n"));
    782829    #endif
    783830
    … …  
    799846    #ifdef ALLWAYS_HEAPCHECK
    800847        if (!_res_heap_check())
    801             kprintf(("_validptr: _res_heap_check failed!\n"));
     848            kprintf(("_res_validptr: _res_heap_check failed!\n"));
    802849    #endif
    803850
    … …  
    820867    #ifdef ALLWAYS_HEAPCHECK
    821868        if (!_res_heap_check())
    822             kprintf(("_validptr: _res_heap_check failed!\n"));
     869            kprintf(("_res_validptr: _res_heap_check failed!\n"));
    823870    #endif
    824871
    … …  
    843890    #ifdef ALLWAYS_HEAPCHECK
    844891        if (!_res_heap_check())
    845             kprintf(("res_memfree: _res_heap_check failed!\n"));
     892            kprintf(("_res_memfree: _res_heap_check failed!\n"));
    846893    #endif
    847894
    … …  
    9881035            else
    9891036            {
    990                 PMEMBLOCKFREE pmbf = (PMEMBLOCKFREE)AVLGet((PPAVLNODECORE)&pha->pcoreFreeSize, pmbFree->cbSize);
     1037                PMEMBLOCKFREE pmbf = (PMEMBLOCKFREE)AVLGet(&pha->pcoreFreeSize, pmbFree->cbSize);
    9911038                if (pmbf != NULL)
    9921039                {
    … …  
    11271174    if (pNode == NULL)
    11281175        return 0;
    1129     if (pNode->Key < 4 || (pNode->Key % 4) != 0)
     1176    if (pNode->Key < 4 || (pNode->Key % ALIGNMENT) != 0)
    11301177    {
    11311178        kprintf(("resCheckAVLTreeFree: Invalid Key! 0x%08x\n", pNode->Key));
    … …  
    12081255            #endif
    12091256            if (rc != NO_ERROR)
    1210                 kprintf(("_res_heapmin: DosFreeMem failed for pha=0x%08x, rc = %d\n",
     1257                kprintf(("_res_heapmin: DosFreeMem/D32Help_VMFree failed for pha=0x%08x, rc = %d\n",
    12111258                         pha, rc));
    12121259        }
Note: See TracChangeset for help on using the changeset viewer.