/*

* Copyright 2012 The Netty Project

*

* The Netty Project licenses this file to you under the Apache License,

* version 2.0 (the "License"); you may not use this file except in compliance

* with the License. You may obtain a copy of the License at:

*

* http://www.apache.org/licenses/LICENSE-2.0

*

* Unless required by applicable law or agreed to in writing, software

* distributed under the License is distributed on an "AS IS" BASIS, WITHOUT

* WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the

* License for the specific language governing permissions and limitations

* under the License.

*/

package io.netty.buffer;

final class PoolSubpage<T> implements PoolSubpageMetric {

final PoolChunk<T> chunk;

private final int memoryMapIdx;

private final int runOffset;

private final int pageSize;

private final long[] bitmap;

PoolSubpage<T> prev;

PoolSubpage<T> next;

boolean doNotDestroy;

int elemSize;

private int maxNumElems;

private int bitmapLength;

private int nextAvail;

private int numAvail;

// TODO: Test if adding padding helps under contention

//private long pad0, pad1, pad2, pad3, pad4, pad5, pad6, pad7;

/** Special constructor that creates a linked list head */

PoolSubpage(int pageSize) {

chunk = null;

memoryMapIdx = -1;

runOffset = -1;

elemSize = -1;

this.pageSize = pageSize;

bitmap = null;

}

PoolSubpage(PoolSubpage<T> head, PoolChunk<T> chunk, int memoryMapIdx, int runOffset, int pageSize, int elemSize) {

this.chunk = chunk;

this.memoryMapIdx = memoryMapIdx;

this.runOffset = runOffset;

this.pageSize = pageSize;

bitmap = new long[pageSize >>> 10]; // pageSize / 16 / 64

init(head, elemSize);

}

void init(PoolSubpage<T> head, int elemSize) {

doNotDestroy = true;

this.elemSize = elemSize;

if (elemSize != 0) {

maxNumElems = numAvail = pageSize / elemSize;

nextAvail = 0;

bitmapLength = maxNumElems >>> 6;

if ((maxNumElems & 63) != 0) {

bitmapLength ++;

}

for (int i = 0; i < bitmapLength; i ++) {

bitmap[i] = 0;

}

}

addToPool(head);

}

/**

* Returns the bitmap index of the subpage allocation.

*/

long allocate() {

if (elemSize == 0) {

return toHandle(0);

}

if (numAvail == 0 || !doNotDestroy) {

return -1;

}

final int bitmapIdx = getNextAvail();

int q = bitmapIdx >>> 6;

int r = bitmapIdx & 63;

assert (bitmap[q] >>> r & 1) == 0;

bitmap[q] |= 1L << r;

if (-- numAvail == 0) {

removeFromPool();

}

return toHandle(bitmapIdx);

}

/**

* @return {@code true} if this subpage is in use.

* {@code false} if this subpage is not used by its chunk and thus it's OK to be released.

*/

boolean free(PoolSubpage<T> head, int bitmapIdx) {

if (elemSize == 0) {

return true;

}

int q = bitmapIdx >>> 6;

int r = bitmapIdx & 63;

assert (bitmap[q] >>> r & 1) != 0;

bitmap[q] ^= 1L << r;

setNextAvail(bitmapIdx);

if (numAvail ++ == 0) {

addToPool(head);

return true;

}

if (numAvail != maxNumElems) {

return true;

} else {

// Subpage not in use (numAvail == maxNumElems)

if (prev == next) {

// Do not remove if this subpage is the only one left in the pool.

return true;

}

// Remove this subpage from the pool if there are other subpages left in the pool.

doNotDestroy = false;

removeFromPool();

return false;

}

}

private void addToPool(PoolSubpage<T> head) {

assert prev == null && next == null;

prev = head;

next = head.next;

next.prev = this;

head.next = this;

}

private void removeFromPool() {

assert prev != null && next != null;

prev.next = next;

next.prev = prev;

next = null;

prev = null;

}

private void setNextAvail(int bitmapIdx) {

nextAvail = bitmapIdx;

}

private int getNextAvail() {

int nextAvail = this.nextAvail;

if (nextAvail >= 0) {

this.nextAvail = -1;

return nextAvail;

}

return findNextAvail();

}

private int findNextAvail() {

final long[] bitmap = this.bitmap;

final int bitmapLength = this.bitmapLength;

for (int i = 0; i < bitmapLength; i ++) {

long bits = bitmap[i];

if (~bits != 0) {

return findNextAvail0(i, bits);

}

}

return -1;

}

private int findNextAvail0(int i, long bits) {

final int maxNumElems = this.maxNumElems;

final int baseVal = i << 6;

for (int j = 0; j < 64; j ++) {

if ((bits & 1) == 0) {

int val = baseVal | j;

if (val < maxNumElems) {

return val;

} else {

break;

}

}

bits >>>= 1;

}

return -1;

}

private long toHandle(int bitmapIdx) {

return 0x4000000000000000L | (long) bitmapIdx << 32 | memoryMapIdx;

}

@Override

public String toString() {

final boolean doNotDestroy;

final int maxNumElems;

final int numAvail;

final int elemSize;

synchronized (chunk.arena) {

if (!this.doNotDestroy) {

doNotDestroy = false;

// Not used for creating the String.

maxNumElems = numAvail = elemSize = -1;

} else {

doNotDestroy = true;

maxNumElems = this.maxNumElems;

numAvail = this.numAvail;

elemSize = this.elemSize;

}

}

if (!doNotDestroy) {

return "(" + memoryMapIdx + ": not in use)";

}

return "(" + memoryMapIdx + ": " + (maxNumElems - numAvail) + '/' + maxNumElems +

", offset: " + runOffset + ", length: " + pageSize + ", elemSize: " + elemSize + ')';

}

@Override

public int maxNumElements() {

synchronized (chunk.arena) {

return maxNumElems;

}

}

@Override

public int numAvailable() {

synchronized (chunk.arena) {

return numAvail;

}

}

@Override

public int elementSize() {

synchronized (chunk.arena) {

return elemSize;

}

}

@Override

public int pageSize() {

return pageSize;

}

void destroy() {

if (chunk != null) {

chunk.destroy();

}

}

}