SQLite

Check-in [9496b4d378]
Login

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
Timelines: family | ancestors | 2-size-lookaside
Files: files | file ages | folders
SHA3-256: 9496b4d378ed38a8d37b2b5f3d575f17b1d19e1890c3ec3b1d409fbe7026fb89
User & Date: numist 2019-10-18 22:54:54.315
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: 9496b4d378 user: numist tags: 2-size-lookaside)
2019-10-09
17:38
Merge recent fixes and enhancements from trunk. (check-in: 553258c2ed user: drh tags: 2-size-lookaside)
Changes
Unified Diff Ignore Whitespace Patch
Changes to src/lookaside.c.
︙︙
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60

    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;








|








46
47
48
49
50
51
52
53
54
55
56
57
58
59
60

    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;
︙︙
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
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182

}

# 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;
    }else{
      assert( pLookaside->pMini==pSlot );
      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;








|
|



<
<

|

|





|


|

>
>
>
|
|
<
|
|
<


|














|





|

|
|



|









|



>
>
>
|

|
















|
|








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
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184

}

# 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;
    }else{
      assert( pLookaside->pMini==pSlot );
      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;
︙︙
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278

  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) );








|

|








264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280

  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
︙︙