path: root/indra/llmessage/llbuffer.cpp

/** 
 * @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 "llmutex.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();
		}
	}
	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;
}