Code owners
Assign users and groups as approvers for specific file changes. Learn more.
llbuffer.cpp 17.93 KiB
/**
* @file llbuffer.cpp
* @author Phoenix
* @date 2005-09-20
* @brief Implementation of the segments, buffers, and buffer arrays.
*
* $LicenseInfo:firstyear=2005&license=viewerlgpl$
* Second Life Viewer Source Code
* Copyright (C) 2010, Linden Research, Inc.
*
* This library is free software; you can redistribute it and/or
* modify it under the terms of the GNU Lesser General Public
* License as published by the Free Software Foundation;
* version 2.1 of the License only.
*
* This library is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
* Lesser General Public License for more details.
*
* You should have received a copy of the GNU Lesser General Public
* License along with this library; if not, write to the Free Software
* Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
*
* Linden Research, Inc., 945 Battery Street, San Francisco, CA 94111 USA
* $/LicenseInfo$
*/
#include "linden_common.h"
#include "llbuffer.h"
#include "llmath.h"
#include "llstl.h"
#include "llthread.h"
#include <iterator>
#define ASSERT_LLBUFFERARRAY_MUTEX_LOCKED() llassert(!mMutexp || mMutexp->isSelfLocked())
/**
* LLSegment
*/
LLSegment::LLSegment() :
mChannel(0),
mData(NULL),
mSize(0)
{
}
LLSegment::LLSegment(S32 channel, U8* data, S32 data_len) :
mChannel(channel),
mData(data),
mSize(data_len)
{
}
LLSegment::~LLSegment()
{
}
bool LLSegment::isOnChannel(S32 channel) const
{
return (mChannel == channel);
}
S32 LLSegment::getChannel() const
{
return mChannel;
}
void LLSegment::setChannel(S32 channel){
mChannel = channel;
}
U8* LLSegment::data() const
{
return mData;
}
S32 LLSegment::size() const
{
return mSize;
}
bool LLSegment::operator==(const LLSegment& rhs) const
{
if((mData != rhs.mData)||(mSize != rhs.mSize)||(mChannel != rhs.mChannel))
{
return false;
}
return true;
}
/**
* LLHeapBuffer
*/
LLHeapBuffer::LLHeapBuffer() :
mBuffer(NULL),
mSize(0),
mNextFree(NULL),
mReclaimedBytes(0)
{
const S32 DEFAULT_HEAP_BUFFER_SIZE = 16384;
allocate(DEFAULT_HEAP_BUFFER_SIZE);
}
LLHeapBuffer::LLHeapBuffer(S32 size) :
mBuffer(NULL),
mSize(0),
mNextFree(NULL),
mReclaimedBytes(0)
{
allocate(size);
}
LLHeapBuffer::LLHeapBuffer(const U8* src, S32 len) :
mBuffer(NULL),
mSize(0),
mNextFree(NULL),
mReclaimedBytes(0)
{
if((len > 0) && src)
{
allocate(len);
if(mBuffer)
{
memcpy(mBuffer, src, len); /*Flawfinder: ignore*/
}
}
}
// virtual
LLHeapBuffer::~LLHeapBuffer()
{
delete[] mBuffer;
mBuffer = NULL;
mSize = 0;
mNextFree = NULL;
}
S32 LLHeapBuffer::bytesLeft() const
{
return (mSize - (mNextFree - mBuffer));
}
// virtual
bool LLHeapBuffer::createSegment(
S32 channel,
S32 size,
LLSegment& segment)
{
// get actual size of the segment.
S32 actual_size = llmin(size, (mSize - S32(mNextFree - mBuffer)));
// bail if we cannot build a valid segment
if(actual_size <= 0)
{
return false;
}
// Yay, we're done.
segment = LLSegment(channel, mNextFree, actual_size);
mNextFree += actual_size;
return true;
}
// virtual
bool LLHeapBuffer::reclaimSegment(const LLSegment& segment)
{
if(containsSegment(segment))
{
mReclaimedBytes += segment.size();
if(mReclaimedBytes == mSize)
{
// We have reclaimed all of the memory from this
// buffer. Therefore, we can reset the mNextFree to the
// start of the buffer, and reset the reclaimed bytes.
mReclaimedBytes = 0;
mNextFree = mBuffer;
}
else if(mReclaimedBytes > mSize)
{
LL_WARNS() << "LLHeapBuffer reclaimed more memory than allocated."
<< " This is probably programmer error." << LL_ENDL;
}
return true;
}
return false;
}
// virtual
bool LLHeapBuffer::containsSegment(const LLSegment& segment) const
{
// *NOTE: this check is fairly simple because heap buffers are
// simple contiguous chunks of heap memory.
if((mBuffer > segment.data())
|| ((mBuffer + mSize) < (segment.data() + segment.size())))
{
return false;
}
return true;
}
void LLHeapBuffer::allocate(S32 size)
{
mReclaimedBytes = 0;
mBuffer = new U8[size];
if(mBuffer)
{ mSize = size;
mNextFree = mBuffer;
}
}
/**
* LLBufferArray
*/
LLBufferArray::LLBufferArray() :
mNextBaseChannel(0),
mMutexp(NULL)
{
}
LLBufferArray::~LLBufferArray()
{
std::for_each(mBuffers.begin(), mBuffers.end(), DeletePointer());
mBuffers.clear();
delete mMutexp;
}
// static
LLChannelDescriptors LLBufferArray::makeChannelConsumer(
const LLChannelDescriptors& channels)
{
LLChannelDescriptors rv(channels.out());
return rv;
}
void LLBufferArray::lock()
{
if(mMutexp)
{
mMutexp->lock() ;
}
}
void LLBufferArray::unlock()
{
if(mMutexp)
{
mMutexp->unlock() ;
}
}
LLMutex* LLBufferArray::getMutex()
{
return mMutexp ;
}
void LLBufferArray::setThreaded(bool threaded)
{
if(threaded)
{
if(!mMutexp)
{
mMutexp = new LLMutex(NULL);
}
}
else
{
if(mMutexp)
{
delete mMutexp ;
mMutexp = NULL ;
}
}
}
LLChannelDescriptors LLBufferArray::nextChannel()
{
LLChannelDescriptors rv(mNextBaseChannel++);
return rv;
}
//mMutexp should be locked before calling this.
S32 LLBufferArray::capacity() const
{
ASSERT_LLBUFFERARRAY_MUTEX_LOCKED();
S32 total = 0;
const_buffer_iterator_t iter = mBuffers.begin();
const_buffer_iterator_t end = mBuffers.end();
for(; iter != end; ++iter)
{
total += (*iter)->capacity();
}
return total;
}
bool LLBufferArray::append(S32 channel, const U8* src, S32 len)
{
LLMutexLock lock(mMutexp) ;
std::vector<LLSegment> segments;
if(copyIntoBuffers(channel, src, len, segments))
{
mSegments.insert(mSegments.end(), segments.begin(), segments.end());
return true;
}
return false;
}
//mMutexp should be locked before calling this.
bool LLBufferArray::prepend(S32 channel, const U8* src, S32 len)
{
ASSERT_LLBUFFERARRAY_MUTEX_LOCKED();
std::vector<LLSegment> segments;
if(copyIntoBuffers(channel, src, len, segments))
{
mSegments.insert(mSegments.begin(), segments.begin(), segments.end());
return true;
}
return false;
}
bool LLBufferArray::insertAfter(
segment_iterator_t segment,
S32 channel,
const U8* src,
S32 len)
{
std::vector<LLSegment> segments;
LLMutexLock lock(mMutexp) ;
if(mSegments.end() != segment)
{
++segment;
}
if(copyIntoBuffers(channel, src, len, segments))
{
mSegments.insert(segment, segments.begin(), segments.end());
return true;
}
return false;
}
//mMutexp should be locked before calling this.LLBufferArray::segment_iterator_t LLBufferArray::splitAfter(U8* address)
{
ASSERT_LLBUFFERARRAY_MUTEX_LOCKED();
segment_iterator_t end = mSegments.end();
segment_iterator_t it = getSegment(address);
if(it == end)
{
return end;
}
// We have the location and the segment.
U8* base = (*it).data();
S32 size = (*it).size();
if(address == (base + size))
{
// No need to split, since this is the last byte of the
// segment. We do not want to have zero length segments, since
// that will only incur processing overhead with no advantage.
return it;
}
S32 channel = (*it).getChannel();
LLSegment segment1(channel, base, (address - base) + 1);
*it = segment1;
segment_iterator_t rv = it;
++it;
LLSegment segment2(channel, address + 1, size - (address - base) - 1);
mSegments.insert(it, segment2);
return rv;
}
//mMutexp should be locked before calling this.
LLBufferArray::segment_iterator_t LLBufferArray::beginSegment()
{
ASSERT_LLBUFFERARRAY_MUTEX_LOCKED();
return mSegments.begin();
}
//mMutexp should be locked before calling this.
LLBufferArray::segment_iterator_t LLBufferArray::endSegment()
{
ASSERT_LLBUFFERARRAY_MUTEX_LOCKED();
return mSegments.end();
}
//mMutexp should be locked before calling this.
LLBufferArray::segment_iterator_t LLBufferArray::constructSegmentAfter(
U8* address,
LLSegment& segment)
{
ASSERT_LLBUFFERARRAY_MUTEX_LOCKED();
segment_iterator_t rv = mSegments.begin();
segment_iterator_t end = mSegments.end();
if(!address)
{
if(rv != end)
{
segment = (*rv);
}
}
else
{
// we have an address - find the segment it is in.
for( ; rv != end; ++rv)
{
if((address >= (*rv).data())
&& (address < ((*rv).data() + (*rv).size())))
{
if((++address) < ((*rv).data() + (*rv).size()))
{ // it's in this segment - construct an appropriate
// sub-segment.
segment = LLSegment(
(*rv).getChannel(),
address,
(*rv).size() - (address - (*rv).data()));
}
else
{
++rv;
if(rv != end)
{
segment = (*rv);
}
}
break;
}
}
}
if(rv == end)
{
segment = LLSegment();
}
return rv;
}
//mMutexp should be locked before calling this.
LLBufferArray::segment_iterator_t LLBufferArray::getSegment(U8* address)
{
ASSERT_LLBUFFERARRAY_MUTEX_LOCKED();
segment_iterator_t end = mSegments.end();
if(!address)
{
return end;
}
segment_iterator_t it = mSegments.begin();
for( ; it != end; ++it)
{
if((address >= (*it).data())&&(address < (*it).data() + (*it).size()))
{
// found it.
return it;
}
}
return end;
}
//mMutexp should be locked before calling this.
LLBufferArray::const_segment_iterator_t LLBufferArray::getSegment(
U8* address) const
{
ASSERT_LLBUFFERARRAY_MUTEX_LOCKED();
const_segment_iterator_t end = mSegments.end();
if(!address)
{
return end;
}
const_segment_iterator_t it = mSegments.begin();
for( ; it != end; ++it)
{
if((address >= (*it).data())
&& (address < (*it).data() + (*it).size()))
{
// found it.
return it;
}
}
return end;
}
/*
U8* LLBufferArray::getAddressAfter(U8* address)
{
U8* rv = NULL;
segment_iterator_t it = getSegment(address);
segment_iterator_t end = mSegments.end();
if(it != end)
{
if(++address < ((*it).data() + (*it).size()))
{
// it's in the same segment
rv = address;
}
else
{
// it's in the next segment
if(++it != end)
{
rv = (*it).data();
}
}
}
return rv;
}
*/
S32 LLBufferArray::countAfter(S32 channel, U8* start) const
{
S32 count = 0;
S32 offset = 0;
const_segment_iterator_t it;
LLMutexLock lock(mMutexp) ;
const_segment_iterator_t end = mSegments.end();
if(start)
{
it = getSegment(start);
if(it == end)
{
return count;
}
if(++start < ((*it).data() + (*it).size()))
{
// it's in the same segment
offset = start - (*it).data();
}
else if(++it == end)
{
// it's in the next segment
return count;
}
}
else
{
it = mSegments.begin();
}
while(it != end)
{
if((*it).isOnChannel(channel))
{
count += (*it).size() - offset;
}
offset = 0;
++it;
}
return count;
}
U8* LLBufferArray::readAfter(
S32 channel, U8* start,
U8* dest,
S32& len) const
{
U8* rv = start;
if(!dest || len <= 0)
{
return rv;
}
S32 bytes_left = len;
len = 0;
S32 bytes_to_copy = 0;
const_segment_iterator_t it;
LLMutexLock lock(mMutexp) ;
const_segment_iterator_t end = mSegments.end();
if(start)
{
it = getSegment(start);
if(it == end)
{
return rv;
}
if((++start < ((*it).data() + (*it).size()))
&& (*it).isOnChannel(channel))
{
// copy the data out of this segment
S32 bytes_in_segment = (*it).size() - (start - (*it).data());
bytes_to_copy = llmin(bytes_left, bytes_in_segment);
memcpy(dest, start, bytes_to_copy); /*Flawfinder: ignore*/
len += bytes_to_copy;
bytes_left -= bytes_to_copy;
rv = start + bytes_to_copy - 1;
++it;
}
else
{
++it;
}
}
else
{
it = mSegments.begin();
}
while(bytes_left && (it != end))
{
if(!((*it).isOnChannel(channel)))
{
++it;
continue;
}
bytes_to_copy = llmin(bytes_left, (*it).size());
memcpy(dest + len, (*it).data(), bytes_to_copy); /*Flawfinder: ignore*/
len += bytes_to_copy;
bytes_left -= bytes_to_copy;
rv = (*it).data() + bytes_to_copy - 1;
++it;
}
return rv;
}
U8* LLBufferArray::seek(
S32 channel,
U8* start,
S32 delta) const
{
ASSERT_LLBUFFERARRAY_MUTEX_LOCKED();
const_segment_iterator_t it;
const_segment_iterator_t end = mSegments.end();
U8* rv = start; if(0 == delta)
{
if((U8*)npos == start)
{
// someone is looking for end of data.
segment_list_t::const_reverse_iterator rit = mSegments.rbegin();
segment_list_t::const_reverse_iterator rend = mSegments.rend();
while(rit != rend)
{
if(!((*rit).isOnChannel(channel)))
{
++rit;
continue;
}
rv = (*rit).data() + (*rit).size();
break;
}
}
else if(start)
{
// This is sort of a weird case - check if zero bytes away
// from current position is on channel and return start if
// that is true. Otherwise, return NULL.
it = getSegment(start);
if((it == end) || !(*it).isOnChannel(channel))
{
rv = NULL;
}
}
else
{
// Start is NULL, so return the very first byte on the
// channel, or NULL.
it = mSegments.begin();
while((it != end) && !(*it).isOnChannel(channel))
{
++it;
}
if(it != end)
{
rv = (*it).data();
}
}
return rv;
}
if(start)
{
it = getSegment(start);
if((it != end) && (*it).isOnChannel(channel))
{
if(delta > 0)
{
S32 bytes_in_segment = (*it).size() - (start - (*it).data());
S32 local_delta = llmin(delta, bytes_in_segment);
rv += local_delta;
delta -= local_delta;
++it;
}
else
{
S32 bytes_in_segment = start - (*it).data();
S32 local_delta = llmin(llabs(delta), bytes_in_segment);
rv -= local_delta;
delta += local_delta;
}
}
}
else if(delta < 0)
{
// start is NULL, and delta indicates seeking backwards - // return NULL.
return NULL;
}
else
{
// start is NULL and delta > 0
it = mSegments.begin();
}
if(delta > 0)
{
// At this point, we have an iterator into the segments, and
// are seeking forward until delta is zero or we run out
while(delta && (it != end))
{
if(!((*it).isOnChannel(channel)))
{
++it;
continue;
}
if(delta <= (*it).size())
{
// it's in this segment
rv = (*it).data() + delta;
}
delta -= (*it).size();
++it;
}
if(delta && (it == end))
{
// Whoops - sought past end.
rv = NULL;
}
}
else //if(delta < 0)
{
// We are at the beginning of a segment, and need to search
// backwards.
segment_list_t::const_reverse_iterator rit(it);
segment_list_t::const_reverse_iterator rend = mSegments.rend();
while(delta && (rit != rend))
{
if(!((*rit).isOnChannel(channel)))
{
++rit;
continue;
}
if(llabs(delta) <= (*rit).size())
{
// it's in this segment.
rv = (*rit).data() + (*rit).size() + delta;
delta = 0;
}
else
{
delta += (*rit).size();
}
++rit;
}
if(delta && (rit == rend))
{
// sought past the beginning.
rv = NULL;
}
}
return rv;
}
//test use only
bool LLBufferArray::takeContents(LLBufferArray& source)
{ LLMutexLock lock(mMutexp);
source.lock();
std::copy(
source.mBuffers.begin(),
source.mBuffers.end(),
std::back_insert_iterator<buffer_list_t>(mBuffers));
source.mBuffers.clear();
std::copy(
source.mSegments.begin(),
source.mSegments.end(),
std::back_insert_iterator<segment_list_t>(mSegments));
source.mSegments.clear();
source.mNextBaseChannel = 0;
source.unlock();
return true;
}
//mMutexp should be locked before calling this.
LLBufferArray::segment_iterator_t LLBufferArray::makeSegment(
S32 channel,
S32 len)
{
ASSERT_LLBUFFERARRAY_MUTEX_LOCKED();
// start at the end of the buffers, because it is the most likely
// to have free space.
LLSegment segment;
buffer_list_t::reverse_iterator it = mBuffers.rbegin();
buffer_list_t::reverse_iterator end = mBuffers.rend();
bool made_segment = false;
for(; it != end; ++it)
{
if((*it)->createSegment(channel, len, segment))
{
made_segment = true;
break;
}
}
segment_iterator_t send = mSegments.end();
if(!made_segment)
{
LLBuffer* buf = new LLHeapBuffer;
mBuffers.push_back(buf);
if(!buf->createSegment(channel, len, segment))
{
// failed. this should never happen.
return send;
}
}
// store and return the newly made segment
mSegments.insert(send, segment);
std::list<LLSegment>::reverse_iterator rv = mSegments.rbegin();
++rv;
send = rv.base();
return send;
}
//mMutexp should be locked before calling this.
bool LLBufferArray::eraseSegment(const segment_iterator_t& erase_iter)
{
ASSERT_LLBUFFERARRAY_MUTEX_LOCKED();
// Find out which buffer contains the segment, and if it is found,
// ask it to reclaim the memory.
bool rv = false;
LLSegment segment(*erase_iter);
buffer_iterator_t iter = mBuffers.begin();
buffer_iterator_t end = mBuffers.end(); for(; iter != end; ++iter)
{
// We can safely call reclaimSegment on every buffer, and once
// it returns true, the segment was found.
if((*iter)->reclaimSegment(segment))
{
rv = true;
break;
}
}
// No need to get the return value since we are not interested in
// the interator retured by the call.
(void)mSegments.erase(erase_iter);
return rv;
}
//mMutexp should be locked before calling this.
bool LLBufferArray::copyIntoBuffers(
S32 channel,
const U8* src,
S32 len,
std::vector<LLSegment>& segments)
{
ASSERT_LLBUFFERARRAY_MUTEX_LOCKED();
if(!src || !len) return false;
S32 copied = 0;
LLSegment segment;
buffer_iterator_t it = mBuffers.begin();
buffer_iterator_t end = mBuffers.end();
for(; it != end;)
{
if(!(*it)->createSegment(channel, len, segment))
{
++it;
continue;
}
segments.push_back(segment);
S32 bytes = llmin(segment.size(), len);
memcpy(segment.data(), src + copied, bytes); /* Flawfinder: Ignore */
copied += bytes;
len -= bytes;
if(0 == len)
{
break;
}
}
while(len)
{
LLBuffer* buf = new LLHeapBuffer;
mBuffers.push_back(buf);
if(!buf->createSegment(channel, len, segment))
{
// this totally failed - bail. This is the weird corner
// case were we 'leak' memory. No worries about an actual
// leak - we will still reclaim the memory later, but this
// particular buffer array is hosed for some reason.
// This should never happen.
return false;
}
segments.push_back(segment);
memcpy(segment.data(), src + copied, segment.size()); /*Flawfinder: ignore*/
copied += segment.size();
len -= segment.size();
}
return true;
}