/ Check-in [9496b4d3]
Login
☰Home Timeline Branches

Many hyperlinks are disabled.
Use anonymous login to enable hyperlinks.

Overview
Comment:Use an allocation count and freelist instead of a membership bitfield in the mini lookaside allocator
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | 2-size-lookaside
Files: files | file ages | folders
SHA3-256: 9496b4d378ed38a8d37b2b5f3d575f17b1d19e1890c3ec3b1d409fbe7026fb89
User & Date: numist 2019-10-18 22:54:54
Context
2019-10-18
22:54
Use an allocation count and freelist instead of a membership bitfield in the mini lookaside allocator (Leaf check-in: 9496b4d3 user: numist tags: 2-size-lookaside)
2019-10-09
17:38
Merge recent fixes and enhancements from trunk. (check-in: 553258c2 user: drh tags: 2-size-lookaside)
Changes
Hide Diffs Unified Diffs Ignore Whitespace Patch

Changes to src/lookaside.c. 

46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
..
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105



106
107
108

109
110
111
112
113

114
115
116
117
118
119
120
...
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154



155
156
157
158
159
160
161
162
163
164
...
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
...
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278

    pLookaside->pInit = pLookaside->pFree;
    pLookaside->pFree = 0;
  }
}

#ifndef SQLITE_OMIT_LOOKASIDE

static void *lookasideSlotAlloc(Lookaside *pLookaside, u64 n){
  LookasideSlot *pBuf;
  if( (pBuf = pLookaside->pFree)!=0 ){
    pLookaside->pFree = pBuf->pNext;
    pLookaside->anStat[0]++;
    return (void*)pBuf;
  }else if( (pBuf = pLookaside->pInit)!=0 ){
    pLookaside->pInit = pBuf->pNext;
................................................................................
}

# ifndef SQLITE_OMIT_MINI_LOOKASIDE
#  ifndef SQLITE_MINI_LOOKASIDE_MIN_SLOT_SIZE
#   define SQLITE_MINI_LOOKASIDE_MIN_SLOT_SIZE 128
#  endif

static void *miniLookasideAlloc(Lookaside *pLookaside, u16 n){
  void *p = 0;
  LookasideSlot *pSlot;
  int iMiniSlot;
  
  assert( n<=pLookaside->szMini );
  
  if( !pLookaside->pMini ){
    pSlot = lookasideSlotAlloc(pLookaside, pLookaside->szTrue);
    if( !pSlot ){
      return p;
    }
    bzero(pSlot, sizeof(LookasideSlot));
    pLookaside->pMini = pSlot;
  }else{
    pSlot = pLookaside->pMini;
    assert( pSlot->bMembership );
  }
  
  assert( pSlot->bMembership < (1<<pLookaside->nMini)-1 );

  iMiniSlot = __builtin_ffs(~pSlot->bMembership) - 1;



  assert(iMiniSlot < pLookaside->nMini);
  assert( (pSlot->bMembership&(1<<iMiniSlot))==0 );
  pSlot->bMembership |= 1<<iMiniSlot;


  p = (char *)pSlot + sizeof(LookasideSlot) + (pLookaside->szMini * iMiniSlot);

  /* Remove slot from pMini if it is full of sub-allocations */
  if( pSlot->bMembership == (1<<pLookaside->nMini)-1 ){

    /* Slot is full, dequeue from list */
    if( pSlot->pNext ){
      assert( pSlot->pNext->pPrev == pSlot );
      pSlot->pNext->pPrev = pSlot->pPrev;
    }
    if( pSlot->pPrev ){
      assert( pSlot->pPrev->pNext == pSlot );
................................................................................
      pSlot->pPrev->pNext = pSlot->pNext;
    }else{
      assert( pLookaside->pMini == pSlot );
      pLookaside->pMini = pSlot->pNext;
    }
    pSlot->pNext = pSlot->pPrev = 0;
  }
  return p;
}

static void miniLookasideFree(Lookaside *pLookaside, void *p){
  int iSlotNum = ((u8*)p - (u8*)pLookaside->pStart) / pLookaside->szTrue;
  LookasideSlot *pSlot = (LookasideSlot *)(iSlotNum * pLookaside->szTrue + (u8*)pLookaside->pStart);
  int iMiniSlot = ((u8*)p - ((u8*)pSlot + sizeof(LookasideSlot))) / pLookaside->szMini;
  
  assert( pSlot->bMembership );
  assert( pSlot->bMembership < (1<<pLookaside->nMini) );
  assert( iMiniSlot<pLookaside->nMini );
  
  /* Return slot to pMini list if it was full */
  if( pSlot->bMembership == (1<<pLookaside->nMini)-1 ){
    assert( pSlot->pNext == pSlot->pPrev && pSlot->pPrev == 0 );
    if( pLookaside->pMini ){
      assert( !pLookaside->pMini->pPrev );
      pSlot->pNext = pLookaside->pMini;
      pSlot->pNext->pPrev = pSlot;
    }
    pLookaside->pMini = pSlot;
  }
  
  pSlot->bMembership &= ~(1<<iMiniSlot);
#ifdef SQLITE_DEBUG
  memset(p, 0xaa, pLookaside->szMini);
#endif



  
  /* Return slot to the lookaside pool if it is empty */
  if( pSlot->bMembership == 0 ){
    if( pSlot->pNext ){
      assert( pSlot->pNext->pPrev == pSlot );
      pSlot->pNext->pPrev = pSlot->pPrev;
    }
    if( pSlot->pPrev ){
      assert( pSlot->pPrev->pNext == pSlot );
      pSlot->pPrev->pNext = pSlot->pNext;
................................................................................
      pLookaside->pMini = pSlot->pNext;
    }
    lookasideSlotFree(pLookaside, pSlot);
  }
}

# else
#  define miniLookasideAlloc(A, B) lookasideSlotAlloc(A, B)
#  define miniLookasideFree(A, B) lookasideSlowFree(A, B)
# endif /* !SQLITE_OMIT_MINI_LOOKASIDE */

int sqlite3LookasideOpen(void *pBuf, int sz, int cnt, Lookaside *pLookaside){
  void *pStart;

  if( sqlite3LookasideUsed(pLookaside,0)>0 ){
    return SQLITE_BUSY;
................................................................................
  if( n>pLookaside->sz ){
    if( !pLookaside->bDisable ){
      pLookaside->anStat[1]++;
    }
    return 0;
  }
  if( n<=pLookaside->szMini && pLookaside->nMini > 1 ){
    return miniLookasideAlloc(pLookaside, n);
  }
  return lookasideSlotAlloc(pLookaside, n);
}

/*
** Free memory previously obtained from sqlite3LookasideAlloc().
*/
void sqlite3LookasideFree(Lookaside *pLookaside, void *p){
  assert( sqlite3IsLookaside(pLookaside, p) );








|







 







|
|



<
<

|

|





|


|

|
>
>
>
|
<
<
>
|
<


<
>







 







|





|

|
|



|









|



>
>
>
|

|







 







|
|







 







|

|








46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
..
77
78
79
80
81
82
83
84
85
86
87
88


89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107


108
109

110
111

112
113
114
115
116
117
118
119
...
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
...
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
...
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280

    pLookaside->pInit = pLookaside->pFree;
    pLookaside->pFree = 0;
  }
}

#ifndef SQLITE_OMIT_LOOKASIDE

static void *lookasideSlotAlloc(Lookaside *pLookaside){
  LookasideSlot *pBuf;
  if( (pBuf = pLookaside->pFree)!=0 ){
    pLookaside->pFree = pBuf->pNext;
    pLookaside->anStat[0]++;
    return (void*)pBuf;
  }else if( (pBuf = pLookaside->pInit)!=0 ){
    pLookaside->pInit = pBuf->pNext;
................................................................................
}

# ifndef SQLITE_OMIT_MINI_LOOKASIDE
#  ifndef SQLITE_MINI_LOOKASIDE_MIN_SLOT_SIZE
#   define SQLITE_MINI_LOOKASIDE_MIN_SLOT_SIZE 128
#  endif

static void *miniLookasideAlloc(Lookaside *pLookaside){
  LookasideSlot *pMiniSlot;
  LookasideSlot *pSlot;
  int iMiniSlot;
  


  if( !pLookaside->pMini ){
    pSlot = lookasideSlotAlloc(pLookaside);
    if( !pSlot ){
      return 0;
    }
    bzero(pSlot, sizeof(LookasideSlot));
    pLookaside->pMini = pSlot;
  }else{
    pSlot = pLookaside->pMini;
    assert( pSlot->nAlloc );
  }
  
  assert( pSlot->nAlloc < pLookaside->nMini );

  if( (pMiniSlot = pSlot->pFree) ){
    pSlot->pFree = pMiniSlot->pNext;
  }else{
    iMiniSlot = pSlot->nAlloc;
    assert(iMiniSlot < pLookaside->nMini);


    pMiniSlot = (LookasideSlot *)((char *)pSlot + sizeof(LookasideSlot) + (pLookaside->szMini * iMiniSlot));
  }


  /* Remove slot from pMini if it is full of sub-allocations */

  if( ++(pSlot->nAlloc) == pLookaside->nMini ){
    /* Slot is full, dequeue from list */
    if( pSlot->pNext ){
      assert( pSlot->pNext->pPrev == pSlot );
      pSlot->pNext->pPrev = pSlot->pPrev;
    }
    if( pSlot->pPrev ){
      assert( pSlot->pPrev->pNext == pSlot );
................................................................................
      pSlot->pPrev->pNext = pSlot->pNext;
    }else{
      assert( pLookaside->pMini == pSlot );
      pLookaside->pMini = pSlot->pNext;
    }
    pSlot->pNext = pSlot->pPrev = 0;
  }
  return pMiniSlot;
}

static void miniLookasideFree(Lookaside *pLookaside, void *p){
  int iSlotNum = ((u8*)p - (u8*)pLookaside->pStart) / pLookaside->szTrue;
  LookasideSlot *pSlot = (LookasideSlot *)(iSlotNum * pLookaside->szTrue + (u8*)pLookaside->pStart);
  LookasideSlot *pMiniSlot = (LookasideSlot *)p;
  
  assert( pSlot->nAlloc );
  assert( pSlot->nAlloc <= pLookaside->nMini );
  assert( iMiniSlot<pLookaside->nMini );
  
  /* Return slot to pMini list if it was full */
  if( pSlot->nAlloc==pLookaside->nMini ){
    assert( pSlot->pNext == pSlot->pPrev && pSlot->pPrev == 0 );
    if( pLookaside->pMini ){
      assert( !pLookaside->pMini->pPrev );
      pSlot->pNext = pLookaside->pMini;
      pSlot->pNext->pPrev = pSlot;
    }
    pLookaside->pMini = pSlot;
  }
  

#ifdef SQLITE_DEBUG
  memset(p, 0xaa, pLookaside->szMini);
#endif
  pSlot->nAlloc--;
  pMiniSlot->pNext = pSlot->pFree;
  pSlot->pFree = pMiniSlot;

  /* Return slot to the lookaside pool if it is empty */
  if( pSlot->nAlloc == 0 ){
    if( pSlot->pNext ){
      assert( pSlot->pNext->pPrev == pSlot );
      pSlot->pNext->pPrev = pSlot->pPrev;
    }
    if( pSlot->pPrev ){
      assert( pSlot->pPrev->pNext == pSlot );
      pSlot->pPrev->pNext = pSlot->pNext;
................................................................................
      pLookaside->pMini = pSlot->pNext;
    }
    lookasideSlotFree(pLookaside, pSlot);
  }
}

# else
#  define miniLookasideAlloc(A) lookasideSlotAlloc(A)
#  define miniLookasideFree(A, B) lookasideSlotFree(A, B)
# endif /* !SQLITE_OMIT_MINI_LOOKASIDE */

int sqlite3LookasideOpen(void *pBuf, int sz, int cnt, Lookaside *pLookaside){
  void *pStart;

  if( sqlite3LookasideUsed(pLookaside,0)>0 ){
    return SQLITE_BUSY;
................................................................................
  if( n>pLookaside->sz ){
    if( !pLookaside->bDisable ){
      pLookaside->anStat[1]++;
    }
    return 0;
  }
  if( n<=pLookaside->szMini && pLookaside->nMini > 1 ){
    return miniLookasideAlloc(pLookaside);
  }
  return lookasideSlotAlloc(pLookaside);
}

/*
** Free memory previously obtained from sqlite3LookasideAlloc().
*/
void sqlite3LookasideFree(Lookaside *pLookaside, void *p){
  assert( sqlite3IsLookaside(pLookaside, p) );

Changes to src/sqliteInt.h. 

1296
1297
1298
1299
1300
1301
1302
1303

1304
1305
1306
1307
1308
1309
1310

#endif /* SQLITE_OMIT_MINILOOKASIDE */
};
struct LookasideSlot {
  LookasideSlot *pNext;    /* Next buffer in the list of buffers */
#ifndef SQLITE_OMIT_MINILOOKASIDE
  /* The members below are only valid for slots inside the mini-allocator */
  LookasideSlot *pPrev;    /* Previous partially-used buffer in the list */
  int bMembership;         /* Bitfield tracking sub-allocations within slot */

#endif /* SQLITE_OMIT_MINILOOKASIDE */
};

#define DisableLookaside  db->lookaside.bDisable++;db->lookaside.sz=0
#define EnableLookaside   db->lookaside.bDisable--;\
   db->lookaside.sz=db->lookaside.bDisable?0:db->lookaside.szTrue









|
>








1296
1297
1298
1299
1300
1301
1302
1303
1304
1305
1306
1307
1308
1309
1310
1311

#endif /* SQLITE_OMIT_MINILOOKASIDE */
};
struct LookasideSlot {
  LookasideSlot *pNext;    /* Next buffer in the list of buffers */
#ifndef SQLITE_OMIT_MINILOOKASIDE
  /* The members below are only valid for slots inside the mini-allocator */
  LookasideSlot *pPrev;    /* Previous partially-used buffer in the list */
  u16 nAlloc;              /* Number of sub-allocations ever returned from this slot */
  LookasideSlot *pFree;    /* List of freed sub-allocations */
#endif /* SQLITE_OMIT_MINILOOKASIDE */
};

#define DisableLookaside  db->lookaside.bDisable++;db->lookaside.sz=0
#define EnableLookaside   db->lookaside.bDisable--;\
   db->lookaside.sz=db->lookaside.bDisable?0:db->lookaside.szTrue

This page was generated in about 0.01s by Fossil 2.14 [815b4fc493] 2020-12-04 18:35:21